直接选择排序

直接选择排序的基本思想

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

①初始状态：无序区为R[1..n]，有序区为空。

②第1趟排序：在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

……

③第i趟排序：第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

算法实现

void SelectSort(SeqList R){   
    int i，j，k；   
    for(i=1;i<n;i++){ //做第i趟排序(1≤i≤n-1)
      k=i；     
      for(j=i+1;j<=n;j++){  //在当前无序区R[i..n]中选key最小的记录R[k]      
        if(R[j].key<R[k].key){         
            k=j; //k记下目前找到的最小关键字所在的位置       
            if(k!=i){ //交换R[i]和R[k]        
                R[0]=R[i]；
                R[i]=R[k]；
                R[k]=R[0]； //R[0]作暂存单元      
            } //endif   
        } 
     } //end里层for 
   } //end外层for 
 } //SeleetSort**

算法分析

（1）关键字比较次数
　无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需做n-i次比较，因此，总的比较次数为： n(n-1)/2=0(n2)

（2）记录的移动次数

• 当初始文件为正序时，移动次数为0
• 文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。
• 直接选择排序的平均时间复杂度为O(n2)。

（3）直接选择排序是一个就地排序

（4）稳定性分析

• 直接选择排序是不稳定的