0%

菜鸟学排序:简单选择排序

试想北宋年间某一天,梁山108好汉要上聚义厅开会,开会嘛,自然要论资排辈排排坐。但现在由于某些原因108好汉已经随机次序的坐在了108把椅子上,需要重新排定一下座次。怎么办呢?

这时候,坐在第一把椅子上的哥们先站起来,找一找老大宋江此时正坐在哪里,然后和宋江交换座位,接着,坐在第二把椅子上的兄弟起身,找一找卢老二坐在那里(注意此时不需要回头看第一把坐的谁,因为前面的哥们已经搞定了),同样交换座位,当然,如果刚好卢老二正好坐在第二把椅子上就不用交换了,依次下去,第三把起身交换,第四把起身交换……等108好汉都按次序做好之后,一趟简单的选择排序也就完成了。

由此可见,选择排序的核心就是,给定一个乱序的数组a[n],排定第a[i] (i<n)时(即第a[i]把椅子该坐谁),从a[i]到a[n-1]遍历找出最值,与a[i]交换,如果a[i]刚好就是最值,则不用交换(想象卢老二正好坐在第二把椅子上的情形)。
根据上面的描述,可以给出实现代码如下:

void selectSort(int a[],int length)  
{  
    int index = 0; //记录最值所在位置  
    int temp = 0; //保存中间值  
    //1.遍历整个数组  
    for (int i = 0; i < length; i++) {  
        index = i;  
        for (int j = i + 1; j < length; j++) {   //遍历索引i之后的乱序数组,找出最值(前面的宋江已经做好了,不需要扫描)  
            if (a[index] < a[j]) {  
                index = j;  
            }  
        }  
        if (index != i) {         //如果自身不是最值,则交换(卢老二没有坐在第二把椅子上)  
            temp = a[index];  
            a[index] = a[i];  
            a[i] = temp;  
        }  
    }  
} 

进一步的,还可以提炼一下,第一次排序是从a[0]开始扫描到a[n-1](共比较n-1次),第二次是从a[1]扫描到a[n-1](共比较n-2次)……也就是说,将未排序的数单独看成一个数组的话,每次都是从这个数组的第一个位置开始扫描比较n-i次,即可以用递归实现:

//递归实现  
void selectSortByRecursion(int a[],int length)  
{  
    if (length == 1) {  
        return;  
    }  
      
    int index = 0;  
    int temp = 0; //保存中间值  
    for (int i = 0; i < length; i++) {  
        if (a[index] < a[i]) {  
            index = i;  
        }  
    }//遍历完成后index指向最值所在索引  
  
    if (index!=0) {  
        temp = a[index];  
        a[index] = a[0];  
        a[0] = temp;  
    }  
      
    selectSortByRecursion(a+1,length-1);  
      
}  

其实就是将之前代码的外层for循环改成了递归调用.核心本质未变.