屌丝的常用排序-----three-白红宇

上面文章讲完了和，本次我们来讨论选择排序。

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法(比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面)。

1、普通(单个)选择排序

每遍历一次，记录下最值元素所在位置，遍历结束后，将此最值元素调整到合适的位置。这样一次遍历，只需一次交换，便可将最值放置到合适位置

                         
//成功返回0，失败返回-1
int
select_sort(
int
*arr,
const
int
n)
{ 
    
//判断参数是否正确
    
if
(NULL == arr || 0 >= n)
            
return
-1;
            
     
int
i = 0;    
//循环使用
     
int
j = 0;    
//循环使用
     
int
k = -1;    
//记录比较的下标
     
int
temp;        
//交换时作中间值
     
      
//每次循环只进行一次交换 最多进行n - 1次循环，因此总体上，比冒泡进行交换的次数少
     
for
(i = 0; i < n - 1; i++)
     
{ 
            
//第i次排序时，已经进行了i次大循环，因此已经排好了i个元素  
            
//已排好序的元素0，,...,i-2,i-1  
            
//待排元素为i,i+1,...,n-1  
            
            
k = i;    
//拿i的位置值与后面的值相比较
            
for
(j = i + 1; j < n; i++)
            
{ 
                    
if
(arr[k] < arr[j])
                        
k = j;
            
}
            
            
//判断k值是否有变化，有变量就交换
            
if
(k != i)
            
{ 
                
temp = arr[k];
                
arr[k] = arr[i];
                
arr[i] = temp;
            
}
     
}
     
return
0;
}
        
      

2、二分选择排序

                         
int
select_sort(
int
*arr, 
const
int
n)
{ 
    
//判断参数是否正确
    
if
(NULL == arr || 0 >= n)
        
return
-1;
        
int
i = 0;
    
int
j = 0;
    
int
minpos = -1;
    
int
maxpos = -1;
    
int
temp;
    
//每次循环完进行二次交换 最多进行n/2次循环，因此总体上，比冒普通选择排序的次数少
    
for
(i = 0; i < n / 2; i++)
    
{ 
        
minpos = i;
        
maxpos = i;
        
for
(j = i + 1; j < n; j++)
        
{ 
            
if
(arr[j] > arr[maxpos])
            
{ 
                
maxpos = j;
                
continue
;
            
}      
            
if
(arr[j] < arr[minpos])
            
{ 
                
minpos = j;
            
}
        
}
        
temp = arr[i];
        
arr[i] = arr[minpos];
        
arr[minpos] = temp;
        
if
(maxpos == i)
        
{ 
            
temp = arr[minpos];
            
arr[minpos] = arr[n - 1 - i];
            
arr[n - 1 - i] = temp;
        
}
        
else
        
{ 
            
temp = arr[maxpos];
            
arr[maxpos] = arr[n - 1 - i];
            
arr[n - 1 -i] = temp;
        
}
    
}
    
return
0;
}

             本文转自asd1123509133 51CTO博客，原文链接：http://blog.51cto.com/lisea/1763976，如需转载请自行联系原作者 