直接选择排序

选择排序(Selection Sort)的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。常用的选择排序方法有直接选择排序和堆排序。

直接选择排序的基本思想

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

  • 初始状态:无序区为 R[1..n],有序区为空。
  • 第 1 趟排序:在无序区 R[1..n]中选出关键字最小的记录 R[k],将它与无序区的第 1 个记录 R[1]交换,使 R[1..i]和 R[2..n]分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区。 ……
  • 第 i 趟排序:第i趟排序开始时,当前有序区和无序区分别为 R[1..i-1]和 R[i..n][1≤i≤n-1]。该趟排序从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第 i 个记录 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  
    } //endfor  
 } //SeleetSort  

算法分析

(1)关键字比较次数

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

(2)记录的移动次数

当初始文件为正序时,移动次数为 0

文件初态为反序时,每趟排序均要执行交换操作,总的移动次数取最大值 3(n-1)。

直接选择排序的平均时间复杂度为 O(n2)。

(3)直接选择排序是一个就地排序

(4)稳定性分析

直接选择排序是不稳定的

【例】反例[2,2,1]

联系我们

邮箱 626512443@qq.com
电话 18611320371(微信)
QQ群 235681453

Copyright © 2015-2024

备案号:京ICP备15003423号-3