数据结构概论第9章排序

1、数据结构概论数据结构概论第9章 排序董黎刚浙江工商大学信电学院1. 排序的基本概念9.1 排序的基本概念9.1.1 背景 查找要取得好的效果，做一些预处理很重要，比如排序。 哪些查找要排序？ 折半查找 分块查找要求部分有序 二叉排序树 平衡二叉树9.1 排序的基本概念9.1.2 排序的概念 排序：有n个记录的序列R1，R2，Rn，其相应关键字的序列是K1，K2，Kn 。通过排序，要求找出当前下标序列1，2，n的一种排列p1，p2，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1 Kp2 Kpn ，这样就得到一个按关键字有序的记录序列：Rp1，Rp2，Rpn。评价：排序的含义很简

2、单，但是描述不简单9.1 排序的基本概念9.1.2 排序的概念 整个排序过程完全在内存中进行，称为内部排序。 由于待排序记录数量太大，内存无法容纳全部记录，排序过程中需要借助外部存储设备（简称外存，比如硬盘）才能完成，称为外部排序。 内存的存储容量小，但存取速度高；外存的存储容量大，但速度较低。 外存包括顺序存取设备（比如，磁带）和直接存取设备（比如，磁盘）两类。9.1 排序的基本概念9.1.2 排序的概念 问题：内部排序和外部排序是指排序方法还是某个具体的排序。 回答：一般来说，内部排序和外部排序是指某个具体的排序。而外部排序方法是指空间复杂度相对较大（比如O(n)）的排序算法。 问题：外部

3、排序是因为数据量大还是空间复杂度大？ 回答：外部排序算法的空间复杂度比较大，因此在数据量非常大的时候，内存可能不够排序操作而需要外存空间。9.1 排序的基本概念9.1.2 排序的概念稳定排序和不稳定排序 比如： 1，2，8，2，9，排序后成为1，2，2，8，9，则该排序算法是不稳定的。 假设Ki=Kj(1in，1jn，ij)，若在排序前的序列中Ri领先于Rj(即ij)，经过排序后得到的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的； 反之，当相同关键字的领先关系在排序过程中可能发生变化，则称所用的排序方法是不稳定的。9.1 排序的基本概念9.1.2 排序的概念 问题：稳定排序的好处是什么？

4、 稳定排序算法对多关键字排序有利。比如扑克牌既要排花色（次要顺序），又要排数字（主要顺序）。 先排花色，黑桃在红心之前； 然后排数字，黑桃3和红心3的数字一样。稳定算法还是会保留原来黑桃3在红心3之前的先后关系。9.1 排序的基本概念9.1.2 排序的概念 问题：怎么证明算法是稳定的或者不稳定？ 证明稳定很难，但是证明不稳定只需要提供一个反例。9.1 排序的基本概念9.1.4 排序中需要的存储结构（1）以顺序表作为存储结构排序过程：对记录本身进行物理重排（即通过关键字之间的比较判定，将记录移到合适的位置）。移动操作可能比较多。（2）以（动态）链表作为存储结构排序过程：无须移动记录，仅需修改指针

5、。9.1 排序的基本概念9.1.4 排序中需要的存储结构（3）建立包括关键字和记录位置下标的索引表排序前Keyi8437ti1234Keyi3478ti3241排序后9.1 排序的基本概念9.1.4 排序中需要的存储结构 使用索引表的排序过程： 排序前令索引表包括keyi和ti=i(0in)。 若排序算法中要求交换记录i和记录j，则只需交换keyi和keyj ，ti和tj即可。排序过程中不移动记录本身。 等排序结束后，再按照表中所规定的次序调整各记录。9.1 排序的基本概念9.1.4 排序中需要的存储结构（4）建立只包含记录位置下标的辅助表排序前ti1234ti3241排序后用Keyti方式获

6、得关键字的值9.1 排序的基本概念9.1.4 排序中需要的存储结构 使用辅助表的排序过程： 排序前令辅助表ti=i(0in)。 若排序算法中要求交换记录i和记录j，则只需交换ti和tj即可。排序过程中不移动记录本身。 等排序结束后，再按照表中所规定的次序调整各记录。 索引表或辅助表适合于难于在（动态）链表上实现的排序方法。9.1 排序的基本概念9.1.5 排序算法的评价 时间复杂度 排序算法的时间开销主要是关键字的比较和记录的移动。 执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态，这时就有最好、最差或平均时间复杂度的区分。 空间复杂度 如空间复杂度是O(1)，则称之为就地排序(In

7、-Place Sort)方法。 非就地排序方法一般要求的空间复杂度为O(n)。 稳定性2. 插入类排序（1）9.2.1 背景 插入类排序基本思想：在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。 种类：直接插入、折半插入和希尔排序9.2 插入类排序直接插入和折半插入9.2 插入类排序直接插入和折半插入9.2.1 背景 插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理，此后每次从桌上的牌(无序区)中摸1张并插入左手的牌(有序区)中正确的位置上。 为了找到这个正确的位置，须自左向右(或自右向左)将摸来的牌与左

8、手中已有的牌逐一比较。9.2.2 直接插入排序 排序实例：初始状态 4862 35 77 55 14 35 98 第1趟插入后 48 6235 77 55 14 35 98第2趟插入后 35 48 6277 55 14 35 98 第3趟插入后 35 48 62 7755 14 35 98 第4趟插入后 35 48 55 62 7714 35 98 第5趟插入后 14 35 48 55 62 7735 98 第6趟插入后 14 35 35 48 55 62 7798 第7趟插入后 14 35 35 48 55 62 77 98 9.2 插入类排序直接插入和折半插入大括号内为有序区（当前已排好序

9、的记录子集合），大括号外是无序区。9.2.2 直接插入排序 第4趟插入的过程：开始状态 35 48 62 7755 14 35 98 55 35 48 62 77 14 35 98 55 35 48 62 77 14 35 98 55 35 48 62 77 14 35 98 35 48 55 62 77 14 35 98 9.2 插入类排序直接插入和折半插入大括号内为有序区（当前已排好序的记录子集合），大括号外是无序区。9.2.2 直接插入排序 直接插入排序的动画9.2 插入类排序直接插入和折半插入9.2.2 直接插入排序 算法过程：将第i个记录的关键字Ki从后往前顺次与其前面记录的关键字K

10、i-1，Ki-2，K1进行比较，将所有关键字大于Ki的记录依次向后移动一个位置，直到遇见一个关键字小于或者等于Ki的记录Kj，此时Kj后面必为空位置，将第i个记录插入空位置即可。 算法要点： 使用监视哨r0临时保存待插入的记录； 从后往前查找应插入的位置； 查找与移动用同一循环完成。9.2 插入类排序直接插入和折半插入9.2.2 直接插入排序算法分析 它只需要一个辅助空间r0。空间复杂度是O(1)。 从时间耗费角度来看，主要时间耗费在关键字比较和移动元素上。 最好情况（只需要跟已排好序的最末尾记录比较）：总的比较次数为：n-1，有监视哨情况下，总的移动次数为2（n-1）。9.2 插入类排序直接

11、插入和折半插入9.2.2 直接插入排序算法分析 最坏情况（需要跟已排好序的记录全部进行比较）：总的比较次数为： 。总的移动次数是 ，因此，时间复杂度为O(n2)。 当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。 直接插入排序是稳定的排序方法。9.2 插入类排序直接插入和折半插入2(2)(1)2ninni2(4)(1)(1)2ninni9.2.3 折半插入排序 算法思路：查找插入位置可以用“折半查找”实现，则直接插入排序就变成为折半插入排序。 以上例中插入98为例，采用折半插入排序寻找插入位置：9.2 插入类排序直接插入和折半插入9

12、.2.3 折半插入排序 以上例中第6趟插入98为例，采用折半插入排序寻找插入位置的过程如图所示（low所指的是插入位置）：9.2 插入类排序直接插入和折半插入9.2.3 折半插入排序 如果插入77，采用折半插入排序寻找的插入位置应该是low所指位置的下一个：9.2 插入类排序直接插入和折半插入9.2.3 折半插入排序算法分析 采用折半插入，可减少关键字的比较次数。每插入一个元素，需要比较的次数最大为折半判定树的深度，如插入第i个元素时,则需进行log2i次比较，因此插入n-1个元素的关键字的平均比较次数为O(nlog2n)。 折半插入与直接插入相比较，改善了算法中比较次数的数量级，但其并未改变

13、移动次数，所以折半插入排序的总的时间复杂度仍然是O(n2)。9.2 插入类排序直接插入和折半插入3. 插入类排序（2）9.3 插入类排序希尔排序9.3.1 背景 折半插入对直接插入的改进是减少比较次数。那么移动次数能否减少？ 直接插入和折半插入的移动基本上是相邻位置移动，如果能够实现位置的远程移动，可减少移动次数。希尔排序采用分组插入排序的方法实现了这一点。9.3 插入类排序希尔排序9.3.2 希尔排序 希尔排序的动画9.3 插入类排序希尔排序9.3.2 希尔排序 希尔排序（Shell Sort）又称缩小增量（间隔）法 希尔排序实例假设，增量序列的取值依次为：5，3，1初始状态： 49，38，

14、65，97，76，13，27，49，55，04增量为5的排序后：9.3 插入类排序希尔排序9.3.2 希尔排序 希尔排序实例增量为3的排序后：增量为1的排序后： 04，13，38，27，49，49，55，65，76，97 注意：上例中两个49的位置发生了改变，显然，希尔排序是不稳定排序。13，04，49，38，27，49，55，65，97，769.3 插入类排序希尔排序9.3.2 希尔排序 好的增量序列的共同特征： 最后一个增量必须为1。 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。9.3 插入类排序希尔排序9.3.3 希尔排序性能分析 希尔排序的时间性能优于直接插入排序的原因：

15、当列表初态基本有序或n值较小时，直接插入排序的性能还不错。 在希尔排序能实现远距离的记录间比较和交换，而直接插入排序中只能相邻记录间交换。 Sedgewick等人提出了最差时间复杂度是O(n4/3)的增量序列，比如1, 5, 19, 41, 109, . . . 。 希尔排序是不稳定的。4. 交换类排序9.4 交换类排序9.4.1 背景 交换类排序基本思想：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。 种类：冒泡排序和快速排序9.4 交换类排序9.4.1 背景 冒泡排序可能是同学们最早听说、最不容易被忘记的排序算法，但是它是最差的排序算法之一。 快速

16、排序则是性能最好的排序算法之一。快速排序是英国计算机科学家C.A.R.Hoare（1934-）于1962年提出的一种划分交换排序。它采用了一种分治的策略。9.4 交换类排序9.4.2 冒泡排序 冒泡排序（Bubble Sort）又称为气泡排序，相邻比序法 算法思想：将被排序的记录Ri看作是重量为Ri.key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上飘浮。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。9.4 交换类排序9.4.3 冒泡排序实例 冒泡排序的动画9.4 交换类排序9.4.3 冒泡排序实例49 13 13 13

17、13 1338 49 27 27 27 2765 38 49 38 38 3897 65 38 49 49 4976 97 65 49 49 4913 76 97 65 65 6527 27 76 97 76 7649 49 49 76 97 97初始 第一趟结果 第二趟结果 第三趟结果 第四趟结果 第五趟结果9.4 交换类排序9.4.4 冒泡排序注意点 若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，因此，冒泡排序过程可在此趟排序后终止。 实际使用中，既可以从左到右（或从下到上）冒泡，也可以从右到左（或从上到下）冒泡；既可以冒大数，也可以冒

18、小数。9.4 交换类排序9.4.5 冒泡排序算法分析 算法的最好时间复杂度。若列表的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：Cmin=n-1，Mmin=0。因此，最好的时间复杂度为O(n)。9.4 交换类排序9.4.5 冒泡排序算法分析 算法的最坏时间复杂度。若列表的初始状态是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1in-1)，且每次比较都必须移动记录3次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：Cmax=n(n-1)/2，Mmax=3n(n-1)/2。因此，最坏时间复杂度为O(n2)。9.4

19、交换类排序9.4.5 冒泡排序算法分析 算法的平均时间复杂度为O(n2)。虽然冒泡排序不一定要进行n-1趟，但由于它的记录移动次数较多，故平均时间性能比直接插入排序要差得多。 算法空间复杂度是O(1)，即冒泡排序是就地排序。 冒泡排序是稳定的。9.4 交换类排序9.4.6 快速排序 快速排序（Quick Sort）算法思想：设当前待排序的无序区为Rlow.high，在Rlow.high中任选一个记录（一般选第一个记录）作为枢轴(Pivot)，以此枢轴将当前无序区划分为左、右两个较小的子区间，并使左边子区间中所有记录均小于等于枢轴记录，右边的子区间中所有记录均大于等于枢轴记录。这称为第一次划分。

20、接下来通过划分算法对左、右子区间进行第二次、第三次划分。9.4 交换类排序9.4.6 快速排序 快速排序的动画9.4 交换类排序9.4.7 快速排序实例 快速排序的第一趟划分划分的目的是以第一个记录（即49）为枢轴，把所有记录分成两部分。初始4938659776132749lowhigh初始4938659776132749lowhigh1次交 2738659776134949换之后 low high 2738659776134949 low high 2738659776134949 low high2次交2738499776136549换之后low high设置low和high分别指向第一个

21、和最后一个记录如果low比high指向的关键字值大，就交换9.4 交换类排序9.4.7 快速排序实例2次交2738499776136549换之后low high2738499776136549 low high3次交2738139776496549换之后low high2738139776496549 low high4次交2738134976976549换之后low high2738134976976549low high完成(273813)49(76976549) low/high9.4 交换类排序9.4.8 比较快速排序和希尔排序 在交换角度上，快速排序与希尔排序比较相似，把相邻位置的移

22、动/交换改成不相邻位置的移动/交换。 在处理的“问题规模”角度上，快速排序与希尔排序有点相反，它先处理一个较大规模，然后逐渐把处理的规模降低，最终达到排序的目的。9.4 交换类排序9.4.9 快速排序算法分析 快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。 好的划分是左右区间中的记录数大致相同，坏的划分是1个区间为空，另一个区间比划分前的无序区中记录数少1。前者导致最好时间复杂度，后者导致最坏时间复杂度。 最好时间复杂度情况下，划分的次数为O(log2n)，而每次划分比较次数不超过n，故整个排序过程所需要的关键字比较总次数O(nlog2n)。9.4 交

23、换类排序9.4.9 快速排序算法分析 最坏时间复杂度情况下，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1in-1)，故总的比较次数达到最大值：Cmax = 因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为0(n2)，最好时间复杂度为O(nlog2n)。就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，平均时间复杂度为O(nlog2n)。1111(1)2nniin nnii 9.4 交换类排序9.4.9 快速排序算法分析 空间复杂度。快速排序算法在递归时需要一个栈保存枢轴位置。若每次划分较为均匀，则其递归树的

24、高度为O(log2n)，故递归后需栈空间为O(log2n)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。 快速排序是非稳定的，例如列表2，2，1经过快速排序后会变成1，2，2。5. 选择类排序（1）9.5 选择类排序简单选择和树形选择9.5.1 背景 交换类排序中，交换操作比较多；而选择类排序中，比较操作较多，交换操作较少：通过多次比较找到记录的最后位置后，再一次性交换到位。 选择类排序基本思想：每一趟从待排序的记录中选出关键字最小（或最大）的记录，顺序放在已排好序的记录的最后，直到全部记录排序完毕。 选择类排序种类：简单选择排序、树形选择排序和堆排序9.5 选择类排序简单选择

25、和树形选择9.5.2 简单选择排序 简单选择排序又称为直接选择排序（Straight Selection Sort） 算法思想：第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。共需进行i-1趟比较，直到所有记录排序完成为止。9.5 选择类排序简单选择和树形选择9.5.3 简单选择排序实例初始关键字 49 38 65 97 76 13 27 49第一趟排序后 13 38 65 97 76 49 27 49第二趟排序后 13 27 65 97 76 49 38 49第三趟排序后 13 27 38 97 76 49 65 49第四趟排

26、序后 13 27 38 49 76 97 65 49 第五趟排序后 13 27 38 49 49 97 65 76第六趟排序后 13 27 38 49 49 65 97 76第七趟排序后 13 27 38 49 49 65 76 97最后排序结果 13 27 38 49 49 65 76 979.5 选择类排序简单选择和树形选择9.5.3 简单选择排序实例 简单选择排序的动画9.5 选择类排序简单选择和树形选择9.5.4 简单选择排序算法分析 最好情况下，即待排序记录就已经是正序排列，则不需要移动记录。最坏情况下，即待排序记录按逆序排列，则需要移动记录的次数最多为3（n-1）。 无论记录初始状

27、态如何，在第i趟排序中选出最小关键字的记录，需做n-i次比较，因此，总的比较次数为：n(n-1)/2。因此，平均时间复杂度为O(n2)。 简单选择排序是一个就地排序。 简单选择排序是不稳定的，比如2，2，1，第一趟排序后为1，2，2。9.5 选择类排序简单选择和树形选择9.5.5 树形选择排序 树形选择排序（Tree Selection Sort）（又称锦标赛排序，Tournament Sort） 算法思想：先把待排序的n个记录的关键字两两进行比较，取出较小者。然后再在 n/2 个较小者中，采用同样的方法进行比较选出每两个中的较小者，如此反复，直至选出最小关键字记录为止。9.5 选择类排序简单

28、选择和树形选择9.5.6 树形选择排序实例 初始状态 49 38 65 97 76 13 27 49 下面求最小关键字 从而得到最小关键字139.5 选择类排序简单选择和树形选择9.5.6 树形选择排序实例 下面求次小关键字，把13改成 从而得到最小关键字27。按照这样的方式可以排出其他关键字9.5 选择类排序简单选择和树形选择9.5.7 树形选择排序算法分析 由于含有n个叶子结点的完全二叉数的深度为 log2n +1（根据二叉树性质4），则在树型选择排序中，每选择一个小关键字需要进行 log2n 次比较( 除第一次选择最小关键字需要n-1次比较)，因此其时间复杂度为O(nlog2n)。 移动

29、记录次数不超过比较次数。 故总的算法时间复杂度为O(nlog2n)。6. 选择类排序（2）9.6 选择类排序堆排序9.6.1 背景 树形选择排序比简单选择排序好的地方是把关键字之间的大小关系保存下来以便后面再次利用，减少了比较次数。 堆排序有进一步改善：保存大小关系不再需要额外空间，从而降低了空间复杂度。9.6 选择类排序堆排序9.6.2 堆排序的相关概念 堆是一种特殊的树形结构（而且是完全二叉树），每个结点都有一个值（即每个记录的关键字值）。 堆的特点是根结点的值最小或最大（两者分别称为小根堆和大根堆），且堆中任一子树也是堆。我们这里用的堆实际上是二叉堆(Binary Heap)，类似地可定

30、义k叉堆。9.6 选择类排序堆排序9.6.2 堆排序的相关概念 通常采用顺序结构存储堆。记录存放在数组r1.n之中，各记录按照树的层次遍历顺序对应各结点。9.6 选择类排序堆排序9.6.3 堆排序中的操作 基本操作筛选 当堆顶元素改变时，对堆进行调整（即把待调整记录逐步向下“筛”），使之恢复成为规范的堆。 构建堆 一个任意序列可以建立一个对应的完全二叉树 反复利用“筛选”法，自底向上逐层把所有子树调整为堆，直到将整个完全二叉树调整为堆。9.6 选择类排序堆排序9.6.3 堆排序中的操作 构建堆的实例已知关键字序列：49，38，65，97，76，13，27，49，通过筛选算法建立小根堆。自第n/

31、2个记录开始进行筛选建堆 9.6 选择类排序堆排序9.6.3 堆排序中的操作 构建堆的实例建立小根堆。9.6 选择类排序堆排序9.6.4 堆排序将待排序记录按照堆的定义建初堆，并输出堆顶元素；把堆中的最后一个记录放到堆顶，然后利用筛选法将剩下的元素重新筛选建成为一个新堆，再输出堆顶元素；重复执行步骤n-1次进行筛选,而依次输出的堆顶元素组成一个有序的序列。9.6 选择类排序堆排序9.6.4 堆排序 堆排序实例 9.6 选择类排序堆排序9.6.4 堆排序 堆排序实例 9.6 选择类排序堆排序9.6.4 堆排序 堆排序实例 9.6 选择类排序堆排序9.6.4 堆排序 堆排序实例 9.6 选择类排序

32、堆排序9.6.4 堆排序 堆排序实例 9.6 选择类排序堆排序9.6.4 堆排序 堆排序实例 9.6 选择类排序堆排序9.6.4 堆排序 堆排序实例 9.6 选择类排序堆排序9.6.4 堆排序 堆排序的动画 9.6 选择类排序堆排序9.6.5 堆排序分析 堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。 对深度为k的堆，筛选算法中进行的关键字的比较次数至多为2（k-1）次。 n个结点的完全二叉树的深度为： log2n +1，则调整建新堆时调用筛选过程n-1次总共进行的比较次数不超过：2（ log2(n-1) + log2(n-2) + log22 ） 2n log2n 9.6

33、 选择类排序堆排序9.6.5 堆排序分析 因此，堆排序在最坏情况下，其时间复杂度也为O(nlog2n)，这是堆排序的最大优点。 堆排序是一种不稳定的排序方法 堆排序不适用于待排序记录个数n较少的情况，但对于n较大时还是很有效的。7. 归并排序9.7 归并排序9.7.1 背景 与快速排序一样，归并排序也是采取分治法。 归并排序与树形选择排序有相似性，要注意区别。 归并排序(Merge Sort)基本思想：将两个或两个以上有序列表合并成一个新的有序列表。 在归并排序中，关注最多的就是2路归并。9.7 归并排序9.7.2 两路归并排序算法思想：假设初始序列含有n个记录， 首先将这n个记录看成n个有序

34、的子序列，每个子序列的长度为1，然后两两归并，得到 n/2 个长度为2（n为奇数时，最后一个序列的长度为1）的有序子序列； 在此基础上，再进行两两归并，如此重复，直至得到一个长度为n的有序序列为止。9.7 归并排序9.7.2 两路归并排序 算法实例9.7 归并排序9.7.2 两路归并排序 归并算法的动画9.7 归并排序9.7.3 归并排序算法分析 归并排序中一趟归并中要多次用到2路归并算法，一趟归并排序的操作是调用 n/(2h) 次合并算法将r11n中前后相邻且长度为h的有序段进行两两归并，得到长度为2h的有序段，并存放在r1n中，其时间复杂度为O(n)。 整个归并排序需进行m（m=log2n

35、）趟2路归并，所以无论是在最好情况下还是在最坏情况下，归并排序的时间复杂度都为O（nlog2n）。9.7 归并排序9.7.3 归并排序算法分析 算法采用了顺序表，在实现归并排序时，需要和待排记录等数量的辅助空间，空间复杂度为O(n)。但是，如果采用链表，其实可以实现空间复杂度为O(1)。 是一种稳定的排序方法9.7 归并排序9.7.4 归并排序用于外部排序 归并排序较多用于外部排序。外部排序可分两步，待排序文件中的记录分批读入内存，用某种内部排序方法在内存排序，组成有序的子文件，再存入外存。用某种归并方法（如2路归并法）对子文件进行多路归并，成为较长有序子文件，再记入外存，如此反复，直到整个待

36、排序文件有序。 最初形成有序子文件长取决于内存所能提供排序区大小和最初排序策略，归并路数取决于所能提供排序的外部设备数。9.7 归并排序9.7.4 归并排序用于外部排序 外部排序实例：假设磁盘上存有一文件，共有3600个记录（A1,A2,A3600），页块长为200个记录，供排序使用的缓冲区可提供容纳600个记录的空间，现要对该文件进行排序，排序过程可按如下步骤进行：9.7 归并排序9.7.4 归并排序用于外部排序 第一步：每次将三个页块（600个记录）由外存读到内存，进行内排序，整个文件共得到6个初始顺串R1-R6 （每一个顺串占三个页块），然后把它们写回到磁盘上去。 第二步：将供内排序使用

37、的内存缓冲区分为三块相等的部分（即每块可容纳200个记录），其中两块作为输入缓冲区，一块作为输出缓冲区，然后对各顺串进行两路归并。8. 分配类排序桶排序9.8 分配类排序桶排序9.8.1 背景 之前的排序算法都包括了关键字的两两比较，但是也有不需要比较关键字的排序算法。 分配排序的基本思想：通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶：O(n)。 分配类排序种类：桶排序（ Bucket Sort， 或称箱排序，Bin Sort ）和基数排序。9.8 分配类排序桶排序 基本思想：设置若干个桶，依次扫描待排序的记录R0，R1，Rn-1，把关键字等于k的记录全都装入到第k个桶里

38、(分配)，然后按序号依次将各非空的桶首尾连接起来(收集)。 实例：对扑克牌按照数字排序9.8.2 基本的桶排序9.8 分配类排序桶排序 一般情况下每个桶中存放多少个关键字相同的记录是无法预料的，故桶的类型应设计成链表为宜。 为保证排序是稳定的，分配过程中装箱及收集过程中的连接必须按先进先出原则进行。比如，人队操作将其插入该桶尾部，而出队时从桶顶部开始取。 分配过程的时间是O(n)；收集过程的时间为O(m) （采用链表来存储输入的待排序记录）。因此，桶排序的时间为O(m+n)。若箱子个数m的数量级为O(n)，则桶排序的时间是线性的，即O(n)。9.8.2 基本的桶排序9.8 分配类排序桶排序 假

39、如关键字值不是离散的，而是连续的，这就意味着有无数个关键字取值，为此，需要一个桶中的记录有不同的关键字值。这就产生了扩展的桶排序。9.8.2 基本的桶排序9.8 分配类排序桶排序基本思想： 把0，1)划分为n个大小相同的子区间，每一子区间是一个桶。然后将n个记录分配到各个桶中。 由于同一桶中的记录其关键字不尽相同，所以必须采用关键字比较的排序方法(通常用插入排序)对各个桶进行排序，然后依次将各非空桶中的记录连接(收集)起来即可。 如果关键字的取值不是在0,1),那么可以先进行归一化处理映射到0,1)，然后再进行上述步骤。9.8.3 扩展的桶排序9.8 分配类排序桶排序算法实例： 对R0.9中的

40、关键字为(0.78，0.17，0.39，0.26，0.72，0.94，0.21， 0.12，0.23，0.68)进行桶排序。 设立10个桶，分别是0,0.1),0.1,0.2),0.9,1) 分配关键字。如果所在桶已经有关键字，要进行插入排序。9.8.3 扩展的桶排序9.8 分配类排序桶排序 收集各个桶中的链表，进行首尾相连9.8.3 扩展的桶排序9.8 分配类排序桶排序9.8.3 扩展的桶排序桶排序算法的动画9.8 分配类排序桶排序 分配过程的平均时间复杂度是O(n)，但是最坏情况下所有关键字都进入同一个桶，那么就产生了直接插入排序算法的复杂度，即O(n2)。9.8.3 扩展的桶排序9. 分

41、配类排序基数排序9.9 分配类排序基数排序9.9.1 背景 基数排序是从多关键字排序解决方法中延伸而来 多关键字排序实例：将一副扑克牌的排序过程看成由花色和点数两个关键字进行排序的问题。若规定花色和面值的顺序如下（假设花色的优先级高于点数）：花色：黑桃红桃梅花方块面值点数：A2310JQK因此，排序顺序为：9.9 分配类排序基数排序9.9.2 多关键字及排序 多关键字：列表中有d个独立的关键字 。比如，扑克牌有两个关键字：点数和花色。不妨假设花色的优先级高于点数。 多关键字排序包括：“高位优先”排序。可以采用扩展的桶排序，只使用一次桶排序。“低位优先”排序。从低位开始多次采用桶排序。9.9 分配类排序基数排序如何对扑克牌排序? “高位优先”排序法：先按花色分成有序的四类，在每一类中，按面值从小到大排序。 “低位优先”排序法：有两轮分配与收集。首先按面值从小到大把牌摆成13叠（每叠4张牌），然后将每叠牌按面值的次序收集到一起，再对这些牌按花色摆成4叠，每叠有13张牌，最后把这4叠牌按花色的次序收集到一起。9.9.2 多关键字及排序9.9 分配类排序基数排序9.9.3