|
选择排序(Selection Sort)的基本思想是每一趟从待排序的记录中选出关键字最小的记录顺序放在已排好序的子文件的最后 直到全部记录排序完毕 常用的选择排序方法有直接选择排序和堆排序 直接选择排序(Straight Selection Sort) 直接选择排序的基本思想 n个记录的文件的直接选择排序可经过n趟直接选择排序得到有序结果 ①初始状态无序区为R[n]有序区为空 ②第趟排序 在无序区R[n]中选出关键字最小的记录R[k]将它与无序区的第个记录R[]交换使R[]和R[n]分别变为记录个数 增加个的新有序区和记录个数减少个的新无序区 …… ③第i趟排序 第i趟排序开始时当前有序区和无序区分别为R[i]和R[in](≤i≤n)该趟排序从当前无序区中选出关键字最小 的记录R[k]将它与无序区的第个记录R[i]交换使R[i]和R[i+n]分别变为记录个数增加个的新有序区和记录个数减少 个的新无序区 这样n个记录的文件的直接选择排序可经过n趟直接选择排序得到有序结果 直接选择排序的过程 对初始关键字为和 的文件进行直接选择排序的过程【 参见动画演示 】 算法描述 直接选择排序的具体算法如下 void SelectSort(SeqList R) { int ijk; for(i=;i k=i; for(j=i+1;j<=n;j++) //在当前无序区R[i..n]中选key最小的记录R[k] if(R[j].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 4、算法分析 (1)关键字比较次数 无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需做n-i次比较，因此，总的比较次数为： n(n-1)/2=0(n 2 ) (2)记录的移动次数 当初始文件为正序时，移动次数为0 文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。tw.WiNgWIt.Com 直接选择排序的平均时间复杂度为O(n 2 )。 (3)直接选择排序是一个就地排序 (4)稳定性分析 直接选择排序是不稳定的 【例】反例[2， 2 ，1] |
