选择和基数排序.ppt

堆排序-性能分析 3. 调整“堆顶” n-1 次，总共进行的关键字比较的次数不超过 2 (?log2(n-1)?+ ?log2(n-2)?+ …+log22) 2n(?log2n?) 因此，堆排序的时间复杂度为O(nlogn)。 堆排序的平均性能较接近于最坏性能。 辅助空间为O(1) 4.堆排序是一个不稳定的排序方法。 堆排序-课堂练习 2、请回答下列关于堆的问题 堆的存储表示是顺序的还是链式的？ 设有一个最小堆，即堆中任意结点的关键字都大于它的左右子女的关键字。其具有最大值的元素可能在什么地方 对n个元素进行初始见堆的过程中，最多做多少次数据比较。 基数排序 基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。 1.多关键字的排序 2.链式基数排序 多关键字排序 n 个记录的序列 { R1, R2, …，Rn} 对关键字 (Ki0, Ki1,…,Kid-1) 有序是指： 对于序列中任意两个记录 Ri 和 Rj (1≤ij≤n) 都满足下列(词典)有序关系： (Ki0, Ki1, …,Kid-1) (Kj0, Kj1, …,Kjd-1) 其中: K0 被称为 “最主”位关键字 Kd-1 被称为 “最次”位关键字 多关键字排序 1.最高位优先MSD法 先对K0进行排序，并按 K0 的不同值将记录序列分成若干子序列之后，分别对 K1 进行排序，...…， 依次类推，直至最后对最次位关键字排序完成为止。 * 选择排序和基数排序 选择排序的基本思想 简单选择排序 堆选择排序 小结和作业 基数排序 选择排序的基本思想 选择排序的基本思想： 每一趟从待排序的n-i+1（i=1,2,3,…,n-1）个记录中选出关键字最小的记录，作为有序序列中第i个记录，直到全部记录排序完毕。 1. 直接选择排序 2. 堆选择排序 简单选择排序-基本思想 假设排序过程中，待排记录序列的状态为： 有序序列R[1..i-1] 无序序列 R[i..n] 第 i 趟 简单选择排序 从中选出 关键字最小的记录 有序序列R[1..i] 无序序列 R[i+1..n] 简单选择排序-基本思想 第i趟排序过程： 1）第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n]； 2）该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换 3）使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区 49 13 简单选择排序-例子 65 97 76 13 27 38 1 2 3 4 5 6 7 k j k j j j j k j 49 第一趟 i=1 13 i 13 简单选择排序-例子 65 97 76 49 27 38 1 2 3 4 5 6 7 k j 第二趟： i=2 j j j j k 27 38 27 i 13 简单选择排序-例子 65 97 76 49 38 1 2 3 4 5 6 7 第三趟： i=3 j 27 65 k j j j 38 k 38 13 65 97 76 49 65 1 2 3 4 5 6 7 第四趟： i=4 27 38 97 49 49 i i k 简单选择排序-例子 13 65 97 76 97 65 1 2 3 4 5 6 7 第五趟： i=5 27 38 38 49 76 65 13 65 97 76 97 76 1 2 3 4 5 6 7 第六趟： i=6 27 38 38 49 76 65 97 13 65 97 76 97 97 1 2 3 4 5 6 7 排序结果： 27 38 38 49 76 65 97 i i 简单选择排序-算法 void SelectSort (Elem R[], i