《数据结构(C语言版)第十章_内部排序》.ppt

10.4 选择排序 一、简单选择排序 三、堆排序 二、树型选择排序 一、简单选择排序 假设排序过程中，待排记录序列的状态为： 有序序列R[1..i-1] 无序序列 R[i..n] 第 i 趟 简单选择排序 从中选出 关键字最小的记录 有序序列R[1..i] 无序序列 R[i+1..n] void SelectSort (SqList &L, int n ) { // 对记录序列R[1..n]作简单选择排序。 for (i=1; i<L.length; ++i) { // 选择第 i 小的记录，并交换到位 } } // SelectSort j = SelectMinKey(L, i); // 在 R[i..n] 中选择关键字最小的记录 if (i!=j) L.r[i]←→L.r[j]; // 与第 i 个记录交换 例 初始： [ 49 38 65 97 76 13 27 ] j k k k k k k j j i=1 13 49 一趟： 13 [38 65 97 76 49 27 ] i=2 j j k k k k k 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 时间性能分析： 　　 对 n 个记录进行简单选择排序，所需进行的 关键字间的比较次数 总计为： 　　移动记录的次数，最小值为 0, 最大值为3(n-1) 。 不稳定的 三、堆排序 堆是满足下列性质的数列{k1, k2, …,kn}： 或 堆的定义: {12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 例如: 是小顶堆 {12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49} 不是堆 (小顶堆) (大顶堆) ki k2i k2i+1 若将该数列视作完全二叉树，则 k2i 是 ki 的左孩子； k2i+1 是 ki 的右孩子。 12 36 27 65 49 81 73 55 40 34 98 例如: 是堆 14 不 将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫堆排序。 　 堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。 例如： 建大顶堆 { 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 } { 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 } 交换 98 和 12 重新调整为大顶堆 { 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 } { 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 } （1）如何由一个无序序列建成一个堆？ 堆排序需解决的两个问题: （2）如何在输出堆顶元素之后，调整剩余元素使之成为一个新的堆？ 输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者（或大者）进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。 第二个问题解决方法——筛选: 98 81 49 73 55 64 12 36 27 40 例如: 是大顶堆 12 98 12 81 73 64 12 98 比较 比较 void HeapAdjust (RcdType &H, int s, int m) { // 已知 H.r[s..m]中记录的关键字除 H.r[s] 之外均 // 满足堆的特征，本函数自上而下调整 H.r[s] 的 // 关键字，使 H.