84第9章 排序.ppt

算法分析 从时间上看，快速排序平均计算时间是O(nlog2n)。实验结果表明: 就平均计算时间而言, 快速排序是所有内排序方法中最好的一个。在最坏的情况, 即待排序对象序列已经按其排序码从小到大排好序的情况下，其时间复杂度为O(n2)。 从空间上看，快速排序是递归的，最大递归调用层次数与递归树的高度一致，理想情况为 ?log2(n+1)? 。因此，要求存储开销为 O(log2n)。 快速排序是一种不稳定的排序方法。 9.3.2 快速排序 9.4 选择排序 9.4.1 简单选择排序 基本思想 　每一趟从待排的无序区中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直至记录全部排完。 具体步骤 　首先在无序区R[1..n]中选出关键字最小的记录，将它与R[1]交换。然后在无序区R[2..n]中选出关键字最小的记录，将它与R[2]交换。重复此过程。当第i趟排序时R[1..i-1]已是有序区，从无序区R[i..n]中选出关键字最小的记录R[k]，将它与R[i]交换，使R[1..i]为有序区。可见，整个过程需要n-1趟排序。 例 9.4.1 简单选择排序 初始： [ 49 38 65 97 76 13 27 ] k j j j j j j k k i=1 13 49 一趟： 13 [38 65 97 76 49 27 ] i=2 k k j j j j j 27 38 二趟： 13 27 [65 97 76 49 38 ] 三趟： 13 27 38 [97 76 49 65 ] 四趟： 13 27 38 49 [76 97 65 ] 五趟： 13 27 38 49 65 [97 76 ] 六趟： 13 27 38 49 65 76 [97 ] 排序结束： 13 27 38 49 65 76 97 直接选择算法 void SelectSort(SqList　L){ /* 对R[1..n]进行直接选择排序 */ 　　for(i=1;in;++i){ /*做n-1趟排序*/ 　　　　min=i; /*min记录最小元素下标*/ 　　　　for(j=i+1;j=n;j++) /* 在当前无序区R[i..n]中选关键字最小的记录R[min] */ 　　　　　　if (L.r[j].keyL.r[min].key) 　　　　　　　　min=j; 　　　　if(min!=i){ /* 交换R[i]和R[min] */ 　　　　　　temp=L.r[i]; 　　　　　　L.r[i]=L.r[min]; 　　　　　　L.r[min]=temp; 　　　　} 　　} } 9.4.1 简单选择排序 时间复杂度 时间复杂度 记录移动次数 最好情况：0 最坏情况：3(n-1) 比较次数： 　整个排序过程共需n-1趟比较，在第i趟中需比较n-i次，故总比较次数为： 故直接选择排序的时间复杂度为O（n2）。 9.4.1 简单选择排序 9.4.3 堆排序 基本思想 　堆排序（HeapSort）是对选择排序的一种改进方法，属于树形排序法。在排序过程中，将R[1..n]看成是一棵完全二叉树的顺序存储结构，利用双亲结点和孩子结点间的内在关系来选择关键字最小的记录。 堆的概念 　设有n个元素的序列 k1，k2，…，kn，当且仅当满足下述关系之一时，称之为堆。 Ki≤K2i和Ki≤K2i+1或Ki≥K2i和Ki≥K2i+1 　其中，Ki必是数列中的最大值或最小值，可分别成为大根堆和小根堆。下图是两种堆的示例。 24 12 47 38 85 91 30 53 大根堆 小根堆 排序过程 ⑴ 以初始关键字序列，建立堆； 　⑵ 输出堆顶最小元素； 　⑶ 调整余下的元素，使其成为一个新堆； 　⑷ 重复⑵,⑶ n 次，得到一个有序序列。 9.4.3 堆排序 85 91 36 47 24 16 53 30 实现堆排序关键要解决⑴和⑶两个问题： 一是如何由一个无序序列建成一个堆? 二是输出堆顶元素后，如何调整余下的元素成为一个新堆? 输出堆顶元素后，堆的重建： 　　解决这一问题可采用“筛选法”。筛选法的基本思想为：设有n个