排序思维脑图思维导图

U360683431

2024-07-06

浏览量: 82

排序介绍

内部排序

外部排序

内部排序总结，内部排序，外部排序等内容讲解

树图思维导图提供《排序思维脑图》在线思维导图免费制作，点击“编辑”按钮，可对《排序思维脑图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：b488770869d7e4d026c7e46e8e69119e

思维导图大纲

内部排序

插入排序

算法思想

每次将⼀个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到插入完成

直接插入排序

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表

简单解释一下,假设要排序12,14,11这个数组,就是先把12看成已排序好了的有序表,而14,11则是依次插入到有序表之中,最终得到11,12,14这个有序表

我们可以看出直接插入排序，在每次插入元素时，只是找比他大的元素，然后去搬移数据。这样在排序成功后不会影响数组内每个数的相对位置。所以直接插入排序是稳定的排序

性能

空间复杂度:O(1)

时间复杂度

最好(原本就是有序的):O(n)

最坏(原本逆序):O(n^2)

平均:O(n^2)

稳定性

稳定

适用性:直接插入排序适用于顺序存储和链式存储的新型表,采用链式存储时无需移动元素

折半插入排序

折半插入排序（binary insertion sort）折半插入排序与直接插入排序算法原理相同。只是，在向已排序的数据中插入数据时，采用来折半查找（二分查找）。先取已经排序的序列的中间元素，与待插入的数据进行比较，如果中间元素的值大于待插入的数据，那么待插入的数据属于数组的前半部分，否则属于后半部分。依次类推，不断缩小范围，确定要插入的位置。

注意：一直到 low>high时才停止折半查找。当mid所指元素等于当前元素时,应继续令low=mid+1，以保证“稳定性”。最终应将当前元素插入到low所指位置（即high+1) 代码看书349页

性能

空间复杂度:O(1)

时间复杂度

和直接插入排序相比较，折半插入排序仅仅是减少了比较的次数，而移动总次数并没有发生改变。这个比较次数大概是O(nlogn) ，移动次数没有改变，所以其复杂度和直接插入排序是一样的O(n^2).

比较元素的次数与待排序的初始状态无关,仅取决于表中的元素个数n;而移动次数并未改变是它只依赖于待排序的初始状态

适用性:仅适用于顺序存储的线性表

对于数据量不很大的排序表,折半插入排序往往能表现出很好的性能

希尔排序

基本思想 :希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。

空间复杂度:O(1)

时间复杂度:这个涉及到数学上还未解决的问题,所以其时间复杂度分析比较困难. 当n在某个特定的范围时,时间复杂度约为O(n^1.3),在最坏情况下的时间复杂度是O(n^2)

稳定性:当相同关键字的记录被划分到不同的子表时,可能会改变它们之间的相对次序,因此希尔排序时一种不稳定的排序算法

适用性:仅适用于顺序存储的线性表

交换排序

冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

空间复杂度:O(1)

时间复杂度

最好时间复杂度(初始序列有序):比较次数为n-1,移动次数为0. 时间复杂度为O(n)

最坏时间复杂度(初始序列逆序):O(n^2)

平均时间复杂度:O(n^2)

最坏时间复杂度(初始序列为逆序):需要n-1躺排序,第i趟排序需要进行n-i次关键词比较,而每次比较后都必须移动元素3次来交换元素位置(有一个交换的过程,所以需要移动元素3次)

比较次数:n(n-1)/2

移动次数:3n(n-1)/2

稳定性:稳定

适用性:适用于顺序存储和链式存储的线性表

注意:冒泡排序中所产生的有序子序列一定是全局有序的(不同于直接插入排序),也就是说,有序子序列中的所有元素的关键字一定小于(或大于)无序子序列中所有元素的关键字,这样每趟排序都会将在一个元素放置在其最终的位置上

快速排序

基本思想：快速排序又是一种分而治之思想在排序算法上的典型应用。算法步骤: 从数列中挑出一个元素，称为 "基准"（pivot）; 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

空间复杂度

由于快速排序是递归的,因此需要借助一个递归工作栈来保存每层递归调用的必要信息,其容量与递归调用的最大层数一致(快排所构成的图形是一个二叉树)最好空间复杂度为O(logn);最坏情况下,要进行n-1次递归调用,即栈的深度也就是空间复杂度为O(n);平均情况下,栈的深度是O(logn)

时间复杂度

快排的运行时间与划分是否对称有关,若每⼀次选中的“枢轴”将待排序序列划分为很不均匀的两个部分，则会导致递归深度增加，算法效率变低。比如，初始序列有序或逆序，则快速排序的性能最差（因为每次选择的都是最靠边的元素）。即最坏的时间复杂度为O(n^2);若每次都能做到最平衡的划分,即最好的时间复杂度为O(nlogn)

快排是所有内部排序算法中平均性能最优的排序算法

快排优化

尽量选择可以把数据中分的枢轴元素,而不是从头开始。例如： 1. 选头、中、尾三个位置的元素，取中间值作为枢轴元素； 2. 随机选⼀个元素作为枢轴元素。

稳定性

快排是不稳定的排序算法

适用性

仅适用于顺序存储的线性表

注:在快速排序算法中,并不会产生有序子序列,但每一趟排序后会将上一趟划分的各个无序子表的枢轴(基准)元素放到最终的位置

对所有尚未确定最终位置的所有元素进行一遍处理成为"一趟"排序,因此一次划分≠一趟排序.一次划分可以确定一个元素的最终位置,而一趟排序也许可以确定多个元素的最终位置

选择排序

简单选择排序

每一趟在待排序元素中选取元素值最小(或最大)的元素加入有序子序列。即在一堆数据中，每次挑出最小的或最大的放入其他有序序列中，当选择完所有待排序数据时，排序就完成了。

空间复杂度:O(1)

时间复杂度:O(n^2)

元素比较的次数与序列的初始状态无关,始终是n(n-1)/2次,因此时间复杂度也始终是O(n^2),元素的移动次数很少,不会超过3(n-1)次(一次交换的移动次数是三次,借用了第三方的变量),最好的情况是0次

稳定性

这个排序算法是不稳定的

例:

适用性:简单选择排序适用于顺序存储和链式存储的线性表,以及关键字较少的情况下

堆排序

堆排序算法主要由两部分组成--将列表转换为堆，并将堆中的最大元素添加到列表的末尾，同时保持堆的结构。为了便于实现，我们使用一个最大堆结构，其中最大值总是存在于根部。在将列表转换为堆后，我们从其中取出最大元素并将其添加到列表的末尾。我们重复这个过程，直到堆中的元素数量变为零。这表明我们已经按照正确的顺序排列了列表中的所有项目。父节点的值总是大于子节点的堆成为大顶堆，父节点的值总是小于子节点的值称为小顶堆

堆排序的算法思路 (以构建大根堆的排序方法为例) :首先将待排序数组中的n个元素使用层次排序建立一颗完全二叉树 (可以将堆视为一颗完全二叉树) 之后从最后一个非叶子节点（计算公式为n.length/2-1,也就是n.length/2向下取整)开始，从后往前进行调整构建，调整的规则是：若子节点大于父节点，则将子节点中较大的节点元素与父节点交换(先子节点做比较,后较大的子节点与父节点进行比较,若子节点大于父节点则子节点和父节点进行交换)

完全二叉树定义:完全二叉树的特点是除最后一层节点外其余层全部是满的，并且最后一层的节点也是从左到右进行存储。完全二叉树特点: 1.根节点放在数组的第一个位置：1 2.左儿子：2x 3.右儿子：2x+1 这里的 x 指的是父节点的下标。

堆排序的视频过程:https://www.cs.usfca.edu/~galles/visualization/HeapSort.html

输出堆顶元素后,将堆的最后一个元素与堆顶元素交换,此时对的性质被破坏,需要进行筛选,形成新的堆

时间复杂度

因为我们使用的是二叉树，所以堆的底部包含最大数量的节点。当我们往上走的时候，节点的数量减少了一半。考虑到有'n'个节点，那么从最底层开始的节点数为 n/2 n/4 (在下一级) n/8 以此类推

建立一个堆的时间复杂度

使用create_heap 函数将一个列表转换为一个堆的时间复杂度不是O(log(n))。这是因为当我们创建一个堆时，不是所有的节点都会向下移动O(log(n))次。只有根节点才会这样做。最底层的节点（由n/2给出）根本不会向下移动。倒数第二层的节点（n/4）会向下移动1次，因为下面只剩下一层可以向下移动。最后第三层的节点将向下移动2次，以此类推。因此，如果我们将所有节点的移动次数相乘，在数学上，它将变成一个几何数列，解释如下 (n/2 * 0) + (n/4 * 1) + (n/8 * 2) + (n/16 * 3) + ...h 这里h代表最大堆结构的高度。这个系列的总和，经过计算，最后得到的数值是n/2。因此，create_heap 的时间复杂度变成了O(n)。

插入一个新节点的复杂性

当我们在制作堆的时候插入一个新的值，我们需要采取的最大步骤数得出是O(log(n))。由于我们使用二叉树，我们知道这样一个结构的最大高度总是O(log(n))。当我们在堆中插入一个新的值时，我们将用一个比它大的值来交换它，以保持最大堆的特性。这种交换的数量将是O(log(n))。因此，在建立最大堆时插入一个新值将是O(log(n))。

从堆中删除最大值节点的复杂性

同样地，当我们从堆中移除最大值节点，添加到列表的末尾时，所需的最大步骤数也是O(log(n))。由于我们交换最大值节点直到它降到最底层，我们需要的最大步骤数与插入一个新节点时相同，即O(log(n))。因此，max_heapify 函数的总时间复杂性变成了O(log(n))。

总的时间复杂度

在heapsort 的最后一个函数中，我们利用create_heap ，它运行一次来创建一个堆，运行时间为O(n)。然后使用for-loop，我们为每个节点调用max_heapify ，每当我们在堆中删除或插入一个节点时，都要保持最大堆的特性。由于有'n'个节点，因此，算法的总运行时间变成了O(n(log(n))，我们对每个节点使用max-heapify 函数。

最好时间复杂度:堆排序的最佳情况是当列表中所有要排序的元素都是相同的。在这种情况下，对于'n'数量的节点-- 从堆中移除每个节点只需要一个恒定的运行时间，即O（1）。由于所有的项目都是相同的，所以不需要将任何节点降低或将最大值节点提高。由于我们对每个节点都这样做，所以移动的总数将是n * O(1)。因此，在最好的情况下，运行时间将是O(n)。

综上:最坏,平均时间复杂度都为O(nlogn),而最好时间复杂度为O(n)

空间复杂度

仅使用了常数个辅助空间,所以空间复杂度为O(1)

稳定性

进行筛选时,有可能把后面的相同元素调整到前面去,所以堆排序是一种不稳定的排序算法

例:

适用性:推排序仅适用于顺序存储的线性表

总结:最坏情况下的时间复杂度为O(n(log(n))[列表中的所有元素都是不同的] 最佳情况下的时间复杂度为O(n) [所有元素都是相同的] 。平均情况下的时间复杂度为O(n(log(n)) 空间复杂度为O(1) 总结的推文:https://juejin.cn/post/7119807721766912030

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

例:

算法思路:归并排序算法有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。(归并排序采用了递归的思想)

时间复杂度

每趟归并的时间复杂度为O(n),要进行logn向上取整趟归并 (归并排序也可以看成一个二叉树,看上面的二路归并排序示例) 因此算法的时间复杂度为O(nlogn)

空间复杂度:在这个递归操作中使用了一个单位为n的辅助空间进行循环操作,因此算法的空间复杂度为O(n)

稳定性:不会改变相同关键字的相对次序,因此是一个稳定的排序算法

适用性:适用于顺序存储和链式存储的线性表

注:一般而言,对于N个元素进行k路归并排序时,排序的趟数m满足k^m=N,从而m=logkN,又考虑到m为整数,因此m=logkN向上取整.这和前面的二路归并排序算法是一致的

基数排序

基本思想原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。 MSD：先从高位开始进行排序 LSD：先从低位开始进行排序

算法动画:https://www.cs.usfca.edu/~galles/visualization/RadixSort.html

高位优先法

例如：对于(21, 12, 31, 10, 30)进行基数排序，可以按照以下步骤进行。 1.根据每一位数字，划分组，最多10组，因为基数为10，代表数字0-9。 2.首先看十位数字，从小到大排序后，可以得到(12,10)(21)(31,30)三组数，数字相同的分为一组。 3.再看个位数字，对上述三组分别进行从小到大排序后，得到(10,12)(21)(30,31)，最终得到有序序列。以上基数排序采用最高位优先方法，从高位到低位进行划分，同样还可以采用从最低位开始排序。最高位优先法排序时候必须不断对划分子序列进行排序，编程实现复杂，最低位优先方法可以每次从低位开始对整个序列进行排序，无需划分。

低位优先法

最低位优先法就是从数字的最低为开始，依次分配和收集最低位优先法相较于最高位优先法，最低位优先法不需要分子序列

低位优先可以按照下面的一组数字做出说明：12、 104、 13、 7、 9 按个位数排序是12、13、104、7、9 再根据十位排序104、7、9、12、13 再根据百位排序7、9、12、13、104 这里注意，如果在某一位的数字相同，那么排序结果要根据上一轮的数组确定，举个例子来说：07和09在十分位都是0，但是上一轮排序的时候09是排在07后面的；同样举一个例子，12和13在十分位都是1，但是由于上一轮12是排在13前面，所以在十分位排序的时候，12也要排在13前面。

空间复杂度

一趟排序需要的辅助存储空间为r (r个队列:在链表中则是r个对头指针,r个队尾指针 (在顺序存储中只有r个队列,没有指针) ),但在以后的排序中会反复使用这些队列,使用基数排序的空间复杂度为O(r)

时间复杂度

基数排序需要进行d趟"分配"和"收集"操作.一趟分配需要遍历所有关键字,时间复杂度为O(n);一趟需要收集合并r个队列,时间复杂度为O(r).因此基数排序的时间复杂度为O(d(n+r)),它与序列的初始状态无关

稳定性:每一趟收集和分配都是从前往后进行的,不会交换相同关键字的相对位置,因此基数排序是一种稳定的算法

适用性:适用于顺序存储和链式存储的线性表

内部排序的总结

从时间复杂度来看

简单选择排序,直接插入排序,冒泡排序评价情况下的时间复杂度都为O(n^2)且实现过程也比较简单，但直接插入排序和冒泡排序最好情况下的时间复杂度可以达到 O(n), 而简单选择排序则与序列的初始状态无关。

希尔排序作为插入排序的拓展，对较大规模的数据都可以达到很高的效率，但目前未得出其精确的渐近时间。

堆排序利用了一种称为堆的数据结构，可以在线性时间内完成建堆，且在 O(nlogn) 内完成排序过程。

快速排序基于分治的思想，虽然最坏情况下的时间复杂度会达到 O(n²), 但快速排序的平均性能可以达到 O(nlogn), 在实际应用中常常优于其他排序算法。

归并排序同样基于分治的思想，但由于其分割子序列与初始序列的排列无关，因此它的最好、最坏和平均时间复杂度均为O(nlog₂n) 。

从空间复杂度来看

简单选择排序、插入排序、冒泡排序、希尔排序和堆排序都仅需借助常数个辅助空间。

快速排序需要借助一个递归工作栈，平均大小为 O(log₂n), 当然在最坏情况下可能会增长到O(n)。

二路归并排序在合并操作中需要借助较多的辅助空间用于元素复制，大小为O(n), 虽然有方法能克服这个缺点，但其代价是算法会很复杂而且时间复杂度会增加。

从稳定性来看

插入排序、冒泡排序、归并排序和基数排序是稳定的排序算法

简单选择排序、快速排序、希尔排序和堆排序都是不稳定的排序算法。

平均时间复杂度为O(nlogn) 的稳定排序算法只有归并排序

从适用性来看

折半插入排序、希尔排序、快速排序和堆排序适用于顺序存储

直接插入排序、冒泡排序、简单选择排序、归并排序和基数排序既适用于顺序存储，又适用于链式存储。

根据排序的中间过程判断所采用的排序算法

冒泡排序、简单选择排序和堆排序在每趟处理后都能产生当前的最大值或最小值

快速排序一趟处理至少能确定一个元素的最终位置

各种排序算法的性质

选取排序算法时需要考虑的因素

1)待排序的元素个数n。 2)待排序的元素的初始状态。 3)关键字的结构及其分布情况。 4)稳定性的要求。 5)存储结构及辅助空间的大小限制等。

算法排序小结

若 n 较小，可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动次数较简单选择排序的多，因此当记录本身信息量较大时，用简单选择排序较好。

若n 较大，应采用时间复杂度为O(nlog₂n) 的排序算法：快速排序、堆排序或归并排序。当待排序的关键字随机分布时，快速排序被认为是目前基于比较的内部排序算法中最好的算法。堆排序所需的辅助空间少于快速排序，且不会出现快速排序可能的最坏情况，这两种排序都是不稳定的。若要求稳定且时间复杂度为O(nlog₂n), 可选用归并排序。

若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。

在基于比较的排序算法中，每次比较两个关键字的大小之后，仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的 n 个关键字随机分布时，任何借助于“比较”的排序算法，至少需要O(nlog₂n) 的时间。

若n 很大，记录的关键字位数较少且可以分解时，采用基数排序较好。

当记录本身信息量较大时，为避免耗费大量时间移动记录，可用链表作为存储结构。

外部排序

基本概念:前面介绍过的排序算法都是在内存中进行的(称为内部排序)。而在许多应用中，经常需要对大文件进行排序，因为文件中的记录很多，无法将整个文件复制进内存中进行排序。因此，需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间的交换。这种排序算法就称为外部排序。

排序的基本思路

外部排序通常采用归并排序算法 (分为两个阶段)

①根据内存缓冲区大小，将外存上的文件分成若干长度为C的子文件，依次读入内存并利用内部排序算法对它们进行排序，并将排序后得到的有序子文件重新写回外存，称这些有序子文件为归并段或顺串；

②对这些归并段进行逐趟归并，使归并段(有序子文件)逐渐由小到大，直至得到整个有序文件为止。

例如，一个含有2000个记录的文件，每个磁盘块可容纳125个记录，首先通过8次内部排序得到8个初始归并段R1～R8, 每段都含250条记录。然后对该文件做如图8.15所示的两两归并，直至得到一个有序文件。可以把内存工作区等分为三个缓冲区，如图8.14所示，其中的两个为输入缓冲区，一个为输出缓冲区。首先，从两个输入归并段R1 和 R2 中分别读入一个块，放在输入缓冲区1和输入缓冲区2中。然后，在内存中进行二路归并，归并后的对象顺序存放在输出缓冲区中。若输出缓冲区中对象存满，则将其顺序写到输出归并段(R1 ') 中，再清空输出缓冲区，继续存放归并后的对象。若某个输入缓冲区中的对象取空，则从对应的输入归并段中再读取下一块，继续参加归并。如此继续，直到两个输入归并段中的对象全部读入内存并都归并完成为止。当R1 和 R2 归并完后，再归并R3 和 R4 、R5 和 R6 、最后归并R7 和 R8, 这是一趟归并。再把上趟的结果R1 '和R2' 、R3 '和R4 '两两归并，这又是一趟归并。最后把R1” 和 R2" 两个归并段归并，得到最终的有序文件，一共进行了3趟归并。

二路平衡归并的排序过程

二路归并

排序时间及其优化

在外部排序中实现两两归并时，由于不可能将两个有序段及归并结果段同时存放在内存中，因此需要不停地将数据读出、写入磁盘，而这会耗费大量的时间。一般情况下：外部排序的总时间=内部排序的时间+外存信息读/写的时间+内部归并的时间

显然，外存信息读/写的时间远大于内部排序和内部归并的时间，因此应着力减少I/O 次数。由于外存信息的读/写是以“磁盘块”为单位的，因此可知每趟归并需进行16次读和16次写，3 趟归并加上内部排序时所需进行的读/写，使得总共需进行32×3+32=128次读/写。

若改用4路归并排序，则只需2趟归并，外部排序时的总读/写次数便减至32×2+32=96。因此，增大归并路数，可减少归并趟数，进而减少总的磁盘I/O 次数，如图8.16所示。

四路平衡归并的排序过程

k路平衡归并

一般地，对r 个初始归并段，做k 路平衡归并(即每趟将k 个或k 个以下的有序子文件归并成一个有序子文件)。第一趟可将r 个初始归并段归并为r/k向上取整个归并段，以后每趟归并将 m 个归并段归并成m/k向上取整个归并段，直至最后形成一个大的归并段为止。树的高度-1=「logkr]=归并趟数 S 。可见，只要增大归并路数 k, 或减少初始归并段个数 r, 都能减少归并趟数 S, 进而减少读/写磁盘的次数，达到提高外部排序速度的目的。

多路平衡树

相对于2路归并，多路平衡归并增加了归并路数，从而减少了外存读写的次数，但是单纯增加归并路数会增加内部归并的时间。如果使用2路归并，每得到一个归并后的记录仅需一次比较，而对于k路归并，每得到一个归并后的记录需要进行k-1次比较。k越大，内部归并所耗费的时间代价就越大。如果内部归并增加的代价大于或等于外存读取减少的代价就得不偿失了。这里需要引入一种名为败者树的数据结构，败者树可以在logk次比较中选出k个数据中的最小值。这样能够有效地减少内部归并所带来的时间代价。

败者树

为了使内部归并不受k 的增大的影响，引入了败者树。败者树是树形选择排序的一种变体，可视为一棵完全二叉树。k 个叶结点分别存放 k 个归并段在归并过程中当前参加比较的元素，内部结点用来记忆左右子树中的“失败者”,而让胜利者往上继续进行比较，一直到根结点。若比较两个数，大的为失败者、小的为胜利者，则根结点指向的数为最小数。

败者树

特点

1.是一颗完全二叉树 2.根节点和它的子节点记录败者的标号 3.建立一棵败者树的时间代价为O(nlogn) 4.败者树的建立和重构仅仅涉及到父子节点之间的比较 5.初始构建败者树需要k-1次比较

因为k 路归并的败者树深度为「log,k ]+1, 所以从k 个记录中选择最小关键字，仅需进行logk向上取整次比较。因此总的比较次数约为S(n-1)「log₂k]=「logkr](n-1)「log₂k]=(n-1)「logr] 可见，使用败者树后，内部归并的比较次数与k 无关了。因此，只要内存空间允许，增大归并路数k 将有效地减少归并树的高度，从而减少I/O 次数，提高外部排序的速度。值得说明的是，归并路数 k 并不是越大越好。归并路数k 增大时，相应地需要增加输入缓冲区的个数。若可供使用的内存空间不变，势必要减少每个输入缓冲区的容量，使得内存、外存交换数据的次数增大。当 k 值过大时，虽然归并趟数会减少，但读/写外存的次数仍会增加。

置换 - 选择排序

选择-置换排序是减少初始分段数外排序算法。由于内部排序的方法都是在内存中对数据进行排序的，所以用这些方法得到的归并段长度完全依赖于内存工作区的大小。因而置换-选择排序没有采用先读取数据再排序的方法，而是边读取边排序。

设初始待排文件为 FI, 初始归并段输出文件为FO, 内存工作区为 WA,FO 和 WA 的初始状态为空，WA 可容纳w 个记录。置换-选择算法的步骤如下： 1 ) 从FI 输入w 个记录到工作区WA。 2 ) 从 WA 中选出其中关键字取最小值的记录，记为MINIMAX 记录。 3 ) 将 MINIMAX 记录输出到FO 中去。 4 ) 若 FI 不空，则从FI 输入下一个记录到WA 中。 5 ) 从 WA 中所有关键字比 MINIMAX 记录的关键字大的记录中选出最小关键字记录，作为新的 MINIMAX 记录。 6 ) 重复 3 ) ～ 5 ) , 直至在 WA 中选不出新的 MINIMAX 记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到 FO 中去。 7 ) 重复 2 ) ～ 6 ) , 直至 WA 为空。由此得到全部初始归并段。设待排文件 FI={17,21,05,44,10,12,56,32,29},WA容量为3,排序过程如表8 . 2所示。

上述算法，在 WA 中选择 MINIMAX 记录的过程需利用败者树来实现

最佳归并排序

哈夫曼树

从树中一个结点到另一个结点之间的分支构成两个节点之间的路径，路径上的分支数目称为路径长度。而树的路径长度是从树根到每一个节点的路径长度之和。对于带权的节点的路径长度为从该节点到树根之间的路径程度和节点上权的乘积。树的带权路径长度为书中所有叶子结点的带权路径长度之和。带权路径长度最小的二叉树被称作哈弗曼树。

定义

置换-选择排序生成的分段长度是不相等的，对于这个不相等的分段直接执行多路平衡归并结果不一定最好。例如，置换-选择排序生成初始分段的长度分别为：[9，30，12，18，3，17，2，6，24]，如果使用3-路归并，则其归并树如下：

整个归并需要对外存的读写次数为484，恰好为归并树带权路径长度的两倍。这给了我们提醒，是不是减少归并树的带权路径长度，就能减少外存读写次数呢？答案是肯定的，我们可以针对不同长短的分段，构造一颗哈弗曼树（不一定是二叉树，可以是3叉、4叉等），以减少外存的读写次数。我们称这棵哈弗曼树为最佳归并树。针对上面那个问题，构造如下所示的最佳归并树，即可将外存读写次数从484次减少到446次。

补充虚段

假如有8个初始分段，而要构造一棵三叉的最佳归并树，该怎么办呢？——补充长度为0虚段。例如，针对如下8个分段[9，12，18，3，17，2，6，24]，构造一个三叉的最佳归并树，其结构如下，其中红色的节点为长度为0的虚段，用来辅助归并树的构建。

如何判定添加虚段的数目?

设度为0的结点有no个，度为k的结点有m个，归并树的结点总数为n，则有： n=nk+no （总结点数=度为k的结点数+度为0的结点数） n=knk+1（总结点数=所有结点的度数之和+1）因此，对严格k叉树有no=（k-1)nk+1，由此可得nk=(no-1)/(k-1)。若(n。-1)%(k-1)=0（%为取余运算），则说明这no个叶结点（初始归并段）正好可以构造k叉归并树。此时，内结点有n个。若(n-1)%(k-1)=u≠0，则说明对于这no个叶结点，其中有u个多余，不能包含在k叉归并树中。为构造包含所有no个初始归并段的k叉归并树，应在原有n个内结点的基础上再增加1个内结点。它在归并树中代替了一个叶结点的位置，被代替的叶结点加上刚才多出的u个叶结点，即再加上k-u-1个空归并段，就可以建立归并树。

以图8 . 19为例，用8个归并段构成3叉树， (n₀-1)%(k-1)=(8-1)%(3-1)=1, 说明 7 个归并段刚好可以构成一棵严格3叉树(假设把以5为根的树视为一个叶子)。为此，将叶子5变成一个内结点，再添加3-1-1=1个空归并段，就可以构成一棵严格3叉树。

自由主题思维导图模板大纲

绘制思维导图的原则