第十章 内部排序 ￡10.1 概述 ￡10.5 归并排序 ￡10.2 插入排序 ￡10.6 基数排序 ￡10.3 快速排序 第十章 内部排序 ￡10.1 概述 ￡10.5 归并排序 ￡10.2 插入排序 ￡10.6 基数排序 ￡10.2.1 直接插入排序 ￡10.6.1 多关键字的排序 ￡10.2.2 其他插入排序 ￡10.6.2 链式基数排序 ￡10.2.3 希尔排序 ￡10.3 快速排序 ￡10.4 选择排序 ￡10.4.1 简单选择排序 ￡10.4.2 树形选择排序 ￡10.4.3 堆排序 ￡10.7 各种内部排序方法的比较讨论

￡10.1 概述 （1）相关术语 假设含有n个记录的序列为 {R1, R2, … , Rn} （10 —1） 其相应的关键字序列为 {K1, K2, … , Kn} 需确定1, 2, … , n的一种排列p1, p2, … , pn，使其相应的关键字满足如下的非递 减（或非递增）关系 （10 — 2） 即使式（10—1）的序列成为一个按关键字有序的序列 （10 — 3） 这样一种操作称为排序。 假设Ki = Kj(1≤i≤n, 1≤j≤n, i≠j)(此时Ki和Kj是记录的次关键字)，且在排序 前的序列中Ri领先于Rj（即i < j）。 若在排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的； 若可能使排序后的序列中Rj领先于Ri，则称所用的排序方法是不稳定的。 内部排序：指的是待排序记录存放在计算机随机存储器中进行的排序过程。 外部排序：指的是待排序记录的数量很大，以致内存一次不能容纳全部记录， 在排序过程中尚需对外存进行访问的排序过程。

（2）内部排序的分类 ①按排序过程中依据的不同原则： 1.插入排序； 2.交换排序； 3.选择排序； 4.归并排序； 5.计数排序 ②按排序过程中所需的工作量： 1．简单的排序方法， 其时间复杂度为O(n2)； 2．先进的排序方法，其时间复杂度为O(nlogn)； 3．基数排序，其时间复杂度为O(d*n)。 （3）两种基本操作 ①比较两个关键字的大小； ②将记录从一个位置移动至另一个位置。 （4）存储方式 待排序的记录序列可有下列3中存储方式： ①待排序的一组记录存放在地址连续的一组存储单元上。 ②一组待排序记录存放在静态链表中。在此方式下实现的排序又称 （链）表排序。 ③待排序记录本身存储在一组地址连续的存储单元内，同时另设一 个指示各个记录存储位置的地址向量。在此方式下实现的排序又 称地址排序。

（5）数据类型 待排记录的数据类型设为： #define MAXSIZE 20 //一个用作示例的小顺序表的最大长度 typedef int KeyType; //定义关键字类型为整数类型 typedef struct { KeyType key; //关键字项 InfoType otherinfo; //其他数据项 } RedType; //记录类型 RedType r[MAXSIZE+1]; //r[0]闲置或用作哨兵单元 int length; //顺序表长度 } SqList; //顺序表类型

￡10.2 插入排序 ￡10.2.1 直接插入排序 （1）主要思想 直接插入排序（Straight Insertion Sort）：是一种最简单的排序方法，它 的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记 录数增1的有序表。 （2）算法实现 一般情况下，第i趟直接插入排序的操作为：在含有i－1个记录的有序子序 列r[1..1－1]中插入一个记录r[i]后，变成含有i个记录的有序子序列r[1..i]；并且， 和顺序表查找类似，为了在查找插入位置的过程中避免数组下标出界，在r[0]处 设置监视哨。在自i－1起往前搜索的过程中，可以同时后移记录。 整个排序过程为进行n－1趟插入，即：先将序列中的第1个记录看成是一个 有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字 非递减有序序列为止。

算法10.1如下： void InsertSort (SqList &L) { //对顺序表L作直接插入排序 for (i = 2; i <= L.length; ++ i) if (LT (L.r[i].key, L.r[i－1].key)) { //“<”，需将L.r[i]插入有序子表 L.r[0] = L.r[i]; //复制为哨兵 L.r[i] = L.r[i－1]; for (j = i－2; LT (L.r[0].key, L.r[j].key); ――j) L.r[j + 1] = L.r[j]; //记录后移 L.r[j + 1] = L.r[0]; //插入到正确位置 } } // InsertSort （3）例子 例如，已知待排序的一组记录的初始排列如下所示： 按算法10.1进行直接插入排序的过程如图10.1所示。

[初始关键字]: (49) 38 65 97 76 13 27 49 监视哨 L.r[0] i = 2: (38) (38 49) 65 97 76 13 27 49 i = 3: (65) (38 49 65) 97 76 13 27 49 i = 4: (97) (38 49 65 97) 76 13 27 49 i = 5: (76) (38 49 65 76 97) 13 27 49 i = 6: (13) (13 38 49 65 76 97) 27 49 i = 7: (27) (13 27 38 49 65 76 97) 49 i = 8: (49) (13 27 38 49 49 65 76 97) 图10.1 直接插入排序示例

（4）算法效率 从空间来看，只需要一个记录的辅助空间。 从时间来看，排序的基本操作为：比较两个关键字的大小和移动记录。 ①当待排序列中记录按关键字非递减有序排序（“正序”）时，所需进行关 键字间比较的次数达最小值n－1（即 ），记录不需移动。 数达最大值(n + 2)(n－1)/2（即 ），记录移动的次数也达最大值 (n + 4)(n－1)/2（即 ）。 ②当待排序列中记录按关键字非递增有序排序（“逆序”）时，总的比较次 ③若待排序记录是随机的，即待排序列中的记录可能出现的各种排列概率 相同，则取上述最小值和最大值的平均值，作为直接插入排序时所需进 行关键字间的比较次数和移动记录的次数，约为n2/4。 综上所述，直接插入排序的时间复杂度为O(n2)。

￡10.2.2 其他插入排序 （1）折半插入排序 ①主要思想 折半插入排序（Binary Insertion Sort）：插入排序的基本操作是在一 个有序表中进行查找和插入，这个“查找 ”操作若利用“折半查找”来实现， 则由此进行的插入排序称为折半插入排序。 ②算法实现 算法10.2如下 void BInertSort (SqList &L) { //对顺序表L作折半插入排序 for (i = 2; i <= L.length; ++ i) { L.r[0] = L.r[i]; //将L.r[i]暂存到L.r[0] low = 1; high = i－1; while (low <= high) { //在r[low..high]中折半查找有序插入的位置 m = (low + high) / 2; //折半 if (LT (L.r[0].key, L.r[m].key)) //插入点在低半区 high = m－1; else low = m + 1; //插入点在高半区 } // while

for (j = i－1; j >= high + 1; ――j) //记录后移 L.r[j + 1] = L.r[j]; L.r[high + 1] = L.r[0]; //插入 } // for } // BInertSort 时间复杂度为：O(n2)。 （2）2-路插入排序 ①主要思想 2-路插入排序是在折半排序的基础上再改进之，其目的是减少排序过程中 移动记录的次数，但为此需要n个记录的辅助空间。 在2-路插入排序中，移动记录的次数约为n2/8。 ②算法实现 另设一个和L.r同类型的数组d，首先将L.r[1]赋值给d[1]，并将d[1]看成是 在排好序的序列中处于中间位置的记录，然后从L.r中第2个记录起依次插入到 d[1]之前或之后的有序序列中。先将待插记录的关键字和d[1]的关键字进行比 较，若L.r[i].key < d[1].key，则将L.r[i]插入到d[1]之前的有序表中。反之，则 将L.r[i]插入到d[1]之后的有序表中。 实现算法时，可将d看成是一个循环向量，并设两个指针first和final分别 指示排序过程中得到的有序序列中的第一个记录和最后一个记录在d中的位置。

③例子 例如，以式 中关键字为例，进行2-路插入排序的过程如图10.2所示。 [初始关键字]: (49) 38 65 97 76 13 27 49 排序过程中d的状态如下： i = 1: (49) first final i = 2: (49) (38) final first i = 3: (49 65) (38) final first i = 4: (49 65 97) (38) final first i = 5: (49 65 76 97) (38) final first i = 6: (49 65 76 97) (13 38) final first i = 7: (49 65 76 97) (13 27 38) final first i = 8: (49 49 65 76 97 13 27 38) final first

SLNode r[SIZE]; //0号单元为表头结点 int length; //链表当前长度 （3）表插入排序 ①主要思想 #define SIZE 100 //静态链表容量 typedef struct { RcdType rc; //记录项 int next; //指针项 } SLNode; //表结点类型 SLNode r[SIZE]; //0号单元为表头结点 int length; //链表当前长度 } SLinkListType; //静态链表类型 以上述静态链表类型作为待排记录序列的存储结构,并 且,设数组中下标为“0”的分量为表头结点,并令表头结 点记录的关键字取最大整数MAXINT。 表插入排序的过程：首先将静态链表中数组下标为“1”的分量（结点）和表 头结点构成一个循环链表，然后依次将下标为“2”至“n”的分量（结点）按记 录关键字非递减有序插入到循环链表中。

③例子 例如，以式 中关键字为例，表插入排序的过程如图10.3所示。 1 0 0 1 2 3 4 5 6 7 8 初始状态 key域 next域 MAXINT 49 38 65 97 76 13 27 49 i = 2 MAXINT 49 38 65 97 76 13 27 49 2 0 1 i = 3 MAXINT 49 38 65 97 76 13 27 49 2 3 1 0 i = 4 MAXINT 49 38 65 97 76 13 27 49 2 3 1 4 0 i = 5 MAXINT 49 38 65 97 76 13 27 49 2 3 1 5 0 4

重排记录：顺序扫描有序链表，将链表中第i个结点移动至数组的第i个分量 0 1 2 3 4 5 6 7 8 key域 next域 MAXINT 49 38 65 97 76 13 27 49 i = 6 6 3 1 5 0 4 2 i = 7 MAXINT 49 38 65 97 76 13 27 49 6 3 1 5 0 4 7 2 i = 8 MAXINT 49 38 65 97 76 13 27 49 6 8 1 5 0 4 7 2 3 图12.3 表插入排序示例 ③ 重排记录 1．算法思想 重排记录：顺序扫描有序链表，将链表中第i个结点移动至数组的第i个分量 中。若第i个最小关键字的结点是数组中下标为p且p > i的分量，则互换SL.r[i]和 SL.r[p]，且令SL.r[i]中的指针域的值改为p；由于此时数组中所有小于i的分量中 已是“到位”的记录，则当p<i时，应顺链继续查找直到p≥i为止。 表插入排序的结果只是求得一个有序链表，则只能对它进行顺序查找，不能 进行随机查找，为了能实现有序表的折半查找，尚需对记录进行重新排列。

2．算法实现 算法10.3如下： void Arrange (SLinkList &SL) { //根据静态链表SL中各结点的指针值调整记录位置，使得SL中记录按关 //键字非递减有序顺序排列 p = SL.r[0].next; //p指示第一个记录的当前位置 for (i = 1; i < SL.length; ++ i) { //SL.r[1..i-１]中记录已按关键字有序排列， //第i个记录在SL中的当前位置应不小于i while (p < i) //找到第i个记录，并用p指示其在SL中当前位置 p = SL.r[p].next; q = SL.r[p].next; //q指示尚未调整的表尾 if (p != i) { SL.r[p]←→SL.r[i]; //交换记录，使第i个记录到位 SL.r[i].next = p; //指向被移走的记录,使得以后可由while循环找回 } p = q; } // for } // Arrange

3．例子 例如，图10.4所示为重排记录的全部过程。 初始状态 MAXINT 49 38 65 97 76 13 27 52 (a) 0 1 2 3 4 5 6 7 8 6 8 1 5 0 4 7 2 3 MAXINT 13 38 65 97 76 49 27 52 (b) i = 1 p = 6 6 (6) 1 5 0 4 8 2 3 (c) i = 2 p = 7 MAXINT 13 27 65 97 76 49 38 52 6 (6) (7) 5 0 4 8 1 3 MAXINT 13 27 38 97 76 49 65 52 6 (6) (7) (7) 0 4 8 5 3 (d) i = 3 p = (2), 7 (e) i = 4 p = (1), 6 MAXINT 13 27 38 49 76 97 65 52 6 (6) (7) (7) (6) 4 0 5 3

0 1 2 3 4 5 6 7 8 (f) i = 5 p = 8 MAXINT 13 27 38 49 52 97 65 76 6 (6) (7) (7) (6) (8) 0 5 4 (g) i = 6 p = (3), 7 MAXINT 13 27 38 49 52 65 97 76 6 (6) (7) (7) (6) (8) (7) 0 4 (h) i = 7 p = (5), 8 MAXINT 13 27 38 49 52 65 76 97 6 (6) (7) (7) (6) (8) (7) (8) 0 图12.4 重排静态链表数组中记录的过程

￡10.2.3 希尔排序 希尔排序（Shell’s Sort）又称“缩小增量排序”(Diminishing Increment Sort)， 它是一种属插入排序类的方法。 （1）主要思想 主要思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排 序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 （2）算法实现 算法10.4如下： void ShellInsert (SqList &L, int dk) { //对顺序表L作一趟希尔排序。本算法和一趟直接插入排序相比,作了如下修改： // 1.前后记录位置的增量是dk，而不是1； // 2.r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到。 for (i = dk+1; i <= L.length; ++ i) if (LT (L.r[i].key, L.r[i－dk].key)) { //需将L.r[i]插入有序增量子表 L.r[0] = L.r[i]; //暂存在L.r[0] L.r[i] = L.r[i－1]; for (j = i－dk; j > 0 && LT (L.r[0].key, L.r[j].key); j―=dk) L.r[j + dk] = L.r[j]; //记录后移，查找插入位置 L.r[j + dk] = L.r[0]; //插入 } } // ShellInsert

算法10.5如下： void ShellSort (SqList &L, int dlta[ ], int t) { //按增量粗鲁dlta[0..t－1]对顺序表L作希尔排序。 for (k = 0; k <t; ++ k) ShellInsert (L, dalta[k]); //一趟增量为dlta[k]的插入排序 } // ShellSort ③例子 例如，以式 中关键字为例，说明希尔排序的过程。 初始关键字序列如图10.5的第1行所示。首先将该序列分成5个子序列：{R1, R6}, {R2, R7}, … , {R5, R10}，分别对每个子序列进行直接插入排序。然后将第1趟希尔排 序的结果分成3个子序列：{R1, R4, R7, R10}, {R2, R5, R8}和{R3, R6, R9}，并对它们进行 直接插入排序。最后对整个序列进行一趟直接插入排序。至此，希尔排序结束，整 个序列的记录已按关键字非递减有序排列。

[初始关键字]: 49 38 65 97 76 13 27 49 55 04 49 13 38 27 97 55 76 04 65 49 一趟排序结果：13 27 49 55 04 49 38 65 97 76 13 55 38 76 27 04 65 49 49 97 二趟排序结果：13 04 49 38 27 49 55 65 97 76 三趟排序结果：04 13 27 38 49 49 55 65 76 97 图10.5 希尔排序示例

（4）特点 希尔排序的特点是：子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。 例如，在上例中，第一趟排序时的增量为5，第二趟排序时的增量为3， 最后一趟排序时为1。

￡10.3 快速排序 （1）起泡排序 起泡排序（Bubble Sort）的过程：首先将第一个记录的关键字和第二个 记录的关键字进行比较，若为逆序（L.r[1].key > L.r[2].key），则将两个记录 交换之，然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1 个记录和第n个记录的关键字进行过比较为止。上述过程称做第一趟起泡排序， 其结果使得关键字最大的记录被安置到最后一个记录的位置上。一般地，第i 趟起泡排序是从L.r[1]到L.r[n-i＋1]依次比较相邻两个记录的关键字，并在“逆 序”时交换相邻记录，其结果是这n-i＋1个记录中关键字最大的记录被交换到 第n-i+1的位置上。整个排序过程需要进行k（1≤k<n）趟起泡排序，显然,判 别起泡排序结束的条件应该是“在一趟排序过程中没有进行过交换记录的操作”。

例如，图10.6展示了起泡排序的一个实例。 49 97 初 第 第 第 第 第 第 始 一 二 三 四 五 六 关 趟 趟 趟 趟 趟 趟 键 排 排 排 排 排 排 字 序 序 序 序 序 序 后 后 后 后 后 后 13 27 49 65 76 13 27 49 49 49 38 38 38 38 13 13 38 49 49 49 13 27 27 65 65 65 13 27 38 38 97 76 13 27 49 49 27 49 76 图10.6 起泡排序示例

总的时间复杂度为O(n2)。 起泡排序的效率： ①若初始序列为“正序”序列，则只需进行一趟排序，在排序过程中进行n-1 次关键字间的比较，且不移动记录； ②若初始序列为“逆序”序列，则需要进行n-1趟排序，需进行 次比较，并作数量级的记录移动。 （2）快速排序 快速排序（Quick Sort）是对起泡排序的一种改进。 ① 主要思想 快速排序的主要思想是：通过一趟排序将待排序记录分割成独立的两部分， 其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分 记录继续进行排序，以达到整个序列有序。 ② 一趟快速排序 假设待排序序列为{L.r[s], L.r[s+1], … , L.r[t]},首先任意选取一个记录（通 常可选为第一个关键字L.r[s]）作为枢轴（或支点）（pivot），然后按下述原 则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将 所有关键字较它大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后 落的位置i作分界线，将序列{L.r[s], … , L.r[t]}分割成两个子序列 {L.r[s], L.r[s+1], … , L.r[i－1]}和{L.r[i＋1], L.r[i+2], … , L.r[t]}。这个过程称做 一趟快速排序（或一次划分）。

一趟快速排序的具体做法是：附设两个指针low和high，它们的初值分别为 low和high，设枢轴记录的关键字为pivotkey，则首先从high所指位置起向前搜 索，找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所 指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交 换，重复这两步直至low＝high为止。其算法如算法10.6(a)所示。 算法10.6(a)如下： int Partition (SqList &L, int low, int high) { //交换顺序表L中子表L.r[low..high]的记录，使枢轴记录到位，并返回其 //所在位置，此时在它之前（后）的记录均不大于（小）于它。 pivotkey = L.r[low].key; //用子表的第一个记录作枢轴记录 while (low < high) { //从表的两端交替地向中间扫描 while (low < high && L.r[high].key >= pivotkey) ――high; L.r[low]←→L.r[high]; //将比枢轴记录小的记录交换到低端 while (low < high && L.r[high].key <= pivotkey) ++ low; L.r[low]←→L.r[high]; //将比枢轴记录大的记录交换到高端 } // while return low; } // Partition

具体实现上述算法时，每交换一对记录需进行3次记录的移动（赋值）的操 作。而实际上，在排序过程中对枢轴记录的赋值是多余的，因为只有在一趟排 序结束时，即low＝high的位置才是枢轴记录的最后位置。由此可改写上述算法， 先将枢轴记录暂存在r[0]的位置上，排序过程中只作r[low]或r[high]的单向移动， 直至一趟排序结束后再将枢轴记录移至正确位置上。如算法10.6(b)所示。 算法10.6(b)如下： int Partition (SqList &L, int low, int high) { //交换顺序表L中子表L.r[low..high]的记录，使枢轴记录到位，并返回其 //所在位置，此时在它之前（后）的记录均不大于（小）于它。 L.r[0] = L.r[low]; //用子表的第一个记录作枢轴记录 pivotkey = L.r[low].key; //枢轴记录关键字 while (low < high) { //从表的两端交替地向中间扫描 while (low < high && L.r[high].key >= pivotkey) ――high; L.r[low] = L.r[high]; //将比枢轴记录小的记录交换到低端 while (low < high && L.r[high].key <= pivotkey) ++ low; L.r [high] = L.r[low]; //将比枢轴记录大的记录交换到高端 } // while L.r[low] = L.r[0]; return low; } // Partition

中关键字为例，一趟快速排序的过程如图10.7(a)所示。 例如，以式 中关键字为例，一趟快速排序的过程如图10.7(a)所示。 pivotkey [初始关键字] 49 38 65 97 76 13 27 49 j i 进行1次交换后 27 38 65 97 76 13 49 j i 进行2次交换后 27 38 97 76 13 65 49 j i 进行3次交换后 27 38 13 97 76 65 49 j i 进行4次交换后 27 38 13 76 97 65 49 j i 完成一趟排序 27 38 13 49 76 97 65 49 (a) 一趟快排过程

③ 快速排序算法实现 整个快速排序的过程可递归进行。若待排序列中只有一个记录，显然已有 序，否则进行一趟快速排序后再分别对分割所得的两个子序列进行快速排序， 如图10.7(b)所示。 初始状态 {49 38 65 97 76 13 27 49} 一次划分之后 {27 38 13} 49 {76 13 27 49} 分别进行快速排序 {13} 27 {38} 结束 结束 {49 65} 76 {97} 49 {65} 结束 结束 有序序列 {13 27 38 49 49 65 76 97} (b) 排序的全过程 图10.7 快速排序示例

算法10.7如下： void QSort (SqList &L, int low, int high) { //对顺序表L中的子序列L.r[low..high]作快速排序 if (low < high) { //长度大于1 pivotloc = Partition (L, low, high); //将L.r[low..high]一分为二 QSort (L, low, pivotloc－1); //对低子表递归排序,pivotloc是枢轴位置 QSort (L, pivotloc + 1, high); //对低高表递归排序 } } // QSort 算法10.8如下： void QuickSort (SqList &L) { //对顺序表L作快速排序 QSort (L, 1, L.length); } // QuickSort ④ 快速排序的平均时间 快速排序的平均时间为： 其中，n为待排序序列中记录的个数，k为某个常数。

⑤ 快速排序的改进 1．“三者取中”法则选取枢轴记录： 即比较L.r[s]、L.r[t].key和 ，取三者中其关键字取中 值的记录为枢轴。 2．修改“一次划分” 算法：在指针high减1和low增1的同时进行“起泡”操作，即在相邻两 个记录处于“逆序”时进行互换，同时在算法中附设两个布尔型变量分别 指示指针low和high在从两端向中间的移动过程中是否进行过交换记录的 操作,若指针low在从低端向中间的移动过程中没有进行交换记录的操作， 则不再需要对低端子表进行排序；类似地，若指针high在从高端向中间 的移动过程中没有进行交换记录的操作,则不再需要对高端子表进行排序。

￡10.4 选择排序 选择排序（Selection Sort）的基本思想是：每一趟n-i+1(i = 1, 2, … , n-1) 个记录中选取关键字最小的记录作为有序序列中第i个记录 ￡10.4.1 简单选择排序 （1）算法实现： 一趟简单选择排序的操作为：通过n-i次关键字间的比较，从n-i+1个记录 中选出关键字最小的记录，并和第i（1≤i≤n）个记录交换之。 对L.r[1..n]中记录进行简单选择排序的算法为：令i从1至n-1，进行n-1趟 选择操作，如算法10.9所示。 算法10.9如下： void SelectSort (SqList &L) { //对顺序表L作简单选择排序 for (i = 1; i < L.length; + + i) { //选择第i小的记录，并交换到位 j = SelectMinkey (L, i); //在中L.r[1..L.length]选择key最小的记录 if (i != j) L.r[i]←→L.r[j]; //与第i个记录交换 } // for } // SelectSort

（2）简单选择排序的改进 选择排序的主要操作是进行关键字间的比较。因此改进简单选择排序 应减少“比较”。 显然，在n个关键字中选出最小值，至少进行n-1次比较，若能利用前 n-1次比较所得信息，则可减少以后各趟选择排序中所用的比较次数。 例如，在8个运动员中决出前3名至多需要11场比赛，而不是7+6+5=18 场比赛（前提：若乙胜丙，甲胜乙，则认为甲必能胜丙）。

￡10.4.2 树形选择排序 出最小关键字的记录为止。这个过程可用一棵有n个叶子结点的完全二叉树表示。 两两比较，然后在其中 个较小者之间再进行两两比较，如此重复，直至选 树形选择排序（Tree Selection Sort）,又称锦标赛排序(Tournament Sort)， 是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行 例如，图10.8(a)中的二叉树表示从8个关键字中选出最小关键字的过程。8 个叶子结点中依次存放排序之前的8个关键字，每个非终端结点中的关键字均等 于其左、右孩子结点中较小的关键字，则根结点中的关键字即为叶子结点中的 最小关键字。 13 38 65 27 49 97 76 (a) 选出最小关键字为13

27 38 65 76 49 97 ∞ 输出13之后 在输出最小关键字 之后，根据关系的可传 递性，欲选出次小关键 字，仅需将叶子结点中 的最小关键字（13）改 为“最大值”，然后从该 叶子结点开始，和其左 （或右）兄弟的关键字 进行比较，修改从叶子 结点到根的路径上各结 点的关键字，则根结点 即为次小关键字。同理, 可依次选出从小到大的 所有关键字。 如图10.8(b)和 (c)所示。 (b) 选出次小关键字为27 38 65 76 49 97 ∞ 输出13，27之后 (c) 选出居第三的关键字为38 图10.8 树形选择排序示例

树形选择排序的时间复杂度：由于含有n个叶子结点的完全二叉树的深度为 ，则在树形选择排序中，除了最小关键字之外，每选择一个次小关键 次比较，因此它的时间复杂度为O(nlog2n)。 字仅需进行

￡10.4.3 堆排序 （1）定义 堆的定义如下：n个元素的序列{k1, k2, … , kn}当且仅当满足以下关系时， 称之为堆。 ki≤k2i 或 ki≤k2i ki≤k2i+1 ki≤k2i+1 例如，下列两个序列为堆{96，83，27，38，11，09}，{12，36，24，85， 47，30，53，91}，对应的完全二叉树如图10.9所示。 96 83 27 11 38 09 12 36 24 47 85 91 53 30 (a) 堆顶元素取最大值 (b) 堆顶元素取最小值 图10.9 堆的示例

堆排序（Heap Sort）：若在输出堆顶的最小值之后，使得剩余n－1个元 得到一个有序序列，这个过程称之为堆排序。堆排序只需要一个记录大小的 辅助空间，每个待排序的记录仅占有一个存储空间。 （2）堆调整 筛选：自堆顶至叶子的调整过程。 例如，图10.10(a)是个堆，假设输出堆顶元素之后，以堆中最后一个元素替 代之，如图10.10(b)所示。此时根结点的左、右子树均为堆，则仅需自上至下进 行调整即可。首先以堆顶元素和其左、右子树根结点的值比较之，由于右子树 根结点的值小于左子树根结点的值且小于根的值，则将27和97交换之；由于97 替代了27之后破坏了右子树的“堆”，则需进行和上述相同的调整，直至叶子结 点，调整后的状态如图10.10(c)所示，此时堆顶为n－1个元素中的最小值。重复 上述过程,将堆顶元素27和和堆中最后一个元素97交换且调整,得到如图10.10(d) 所示新的堆。

13 97 27 38 65 49 13 76 38 27 49 76 65 49 97 (a) 堆 (b) 13和97交换后的情形 27 49 38 65 97 13 76 38 49 27 65 97 13 76 (c) 调整后的新堆 (d) 27和97交换后再进行调整建成的新堆 图10.10 输出堆顶元素并调整健新堆的过程 返回 说明

算法实现： 算法10.10如下： typedef SqList HeapType; //堆采用顺序表存储表示 void HeapAdjust (HeapType &H, int s, int m) { //已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数调整 // H.r[s]的关键字，使H.r[s..m]成为一个大顶堆（对其中记录的关键字而言）。 rc = H.r[s]; for (j = 2*s; j <= m; j *=2) { //沿key较大的孩子结点向下筛选 if (j < m && LT(H.r[j].key, H.r[j + 1].key) + + j; //j为key较大的记录的下标 if (!LT(rc.key, H.r[j].key)) //rc应插入在位置s上 break; H.r[s] = H.R[j]; s = j; } // for H.r[s] = rc; //插入 } // HeapAdjust （3）建堆 从一个无序序列建堆的过程就是一个反复“筛选”的过程。若将此序列看成是 一棵完全二叉树，则最后一个非终端结点是第 个元素开始。 个元素,由此“筛选”只需从第

例如，图10.11(a)中的二叉树表示一个有8个元素的无序序列 {49，38，65，97，76，13，27，49} 则筛选从第4个元素开始，由于97 > 49，则交换之，交换后的序列如图 10.11(b)所示，同理，在第3个元素65被筛选之后序列的状态如图10.11(c)所 示。由于第2个元素38不大于其左、右子树根的值，则筛选后的序列不变。 图10.11(e)所示为筛选根元素49之后建成的堆。 38 49 27 65 97 13 76 38 49 27 65 97 13 76 (b) 97被筛选之后的状态 (a) 无序序列

38 49 27 65 97 13 76 (c) 65被筛选之后的状态 38 49 27 65 97 13 76 38 13 49 65 97 27 76 (d) 38被筛选之后的状态 (e) 49被筛选之后的状态 图10.11 建初始堆的过程示例 返回 说明

（4）堆排序 堆排序的算法如算法10.11所示。为使排序结果和前述一致，即使记录序列 按关键字非递减有序排列，则在堆排序的算法中先建一个“大顶堆”，即先选得一 个关键字为最大记录并与序列中最后一个记录交换，然后对序列中前n－1记录进 行筛选，重新将它调整为一个“大顶堆”，如此反复直至排序结束。由此，“筛选” 应沿关键字较大的孩子结点向下进行。 算法10.11如下： void HeapSort (HeapType &H) { //对顺序表H进行堆排序 for (i = H.length/2; i > 0; ――i) //把H.r[1…i]建成大顶堆 HeapAdjust (H, i, H.length); for (i = H.length; i > 1; ――i) { H.r[1]←→H.r[i]; //将堆顶记录和当前未经排序子序列 // H.r[1…i]中最后一个记录相互交换 HeapAdjust (H, 1, i－1); //将H.r[1…i－1]重新调整为大顶堆 } // for } // HeapSort 堆排序在最坏的情况下，其时间复杂度也为 。

￡10.5 归并排序 （1）定义 归并：是指将两个或两个以上的有序表组合成一个新的有序表。 假设初始序列含有n个记录，则可看成是n个有促的子序列，每个子序列 个长度为2或1的有序子序列；再两两 的长度为1，然后两两归并，得到 归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序 方法称为2-路归并排序。 （2）算法实现 2-路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归 并为一个有序序列，其算法如算法10.12所示。

算法10.12如下： void Merge (RcdType SR[ ], RcdType &TR[ ], int i, int m, int n) { //将有序的SR[i..m]和SR[m＋1..n]归并为有序的TR[i..n] for (j = m + 1, k = i; i <= m && j <= n; ++ k) { //将SR中记录由小到大地并入TR if (LQ(SR[i].key, SR[j].key)) TR[k] = SR[i ++]; else TR[k] = SR[j ++]; } // for if (i <= m) TR[k..n] = SR[i..m]; //将剩余的SR[i..m]复制到TR if (j <= n) TR[k..n] = SR[j..n]; //将剩余的SR[j..n]复制到TR } // Merge 排记录等数量的辅助空间，其时间复杂度为 。 一趟归并排序的操作是，调用 次算法merge将SR[1..n]中前后相邻且 趟。可见，实现归并排序需和待 长度为h的有序段进行两两归并，得到前后相邻，长度为2h的有序段，并存放 在TR[1..n]中，整个归并排序需进行

递归形式的2-路归并排序的算法如算法10.13和算法10.14所示。 算法10.13如下： void MSort (RcdType SR[ ], RcdType &TR1[ ], int s, int t) { //将SR[s..t]和SR[m＋1..n]归并排序为TR1[s..t] if (s = = t) TR1[s] = SR[s]; else { m = (s + t) / 2; //将SR[s..t]平分为SR[s..m]和SR[m＋1..t] MSort (SR, TR2, s, m); //递归地将SR[s..m]归并为有序的TR2[s..m] MSort (SR, TR2, m + 1, t); //递归地将SR[m＋1..t]归并为有序的TR2[m＋1..t] Merge (TR1, TR2, s, m, t); //递归地将TR2[s..m]和TR2[m＋1..t]归并到TR1[s..t] } // else } // MSort 算法10.14如下： void MergeSort (SqList &L) { //对顺序表L作归并排序 MSort (L.r, L.r, 1, L.length); } // MergeSort

（3）例子 例如，图10.12为2-路归并排序的一个例子。 [初始关键字] (49) (38) (65) (97) (76) (13) (27) 一趟归并之后 (38 49) (65 97) (13 76) (27) 二趟归并之后 (38 49 65 97) (13 27 76) 三趟归并之后 (13 27 38 49 65 76 97) 图10.12 为2-路归并排序示例

￡10.6 基数排序 ￡10.6.1 多关键字的排序 基数排序（Radix Sorting）是一种借助多关键字排序的思想对单逻辑 关键字进行关系的方法。基数排序不需要进行记录关键字间的比较。 ￡10.6.1 多关键字的排序 （1）定义 假设有n个记录的序列 {R1, R2, … , Rn} （10－4） ，则称序列（10－4）对关键字 有序是指：对于序列中任意两个记录Ri和Rj (1≤i < j≤n)都满足 < 其中K0称为最主位关键字，Kd-1称为最次位关键字。 且每个记录Ri中含有d个关键字 下列有序关系：

（2）多关键字排序的实现 ① 最高位优先MSD（Most Signigicant Digit first） 1．算法实现：先对最主位关键字K0进行排序，将序列分成若干子序 列，每个子序列中的记录都具有相同的K0值，然后分别就每个子序列对 关键字K1进行排序，按K1值不同再分成若干更小的子序列，依次重复， 直至对Kd-2进行排序之后得到的每一子序列中的记录都具有系统的关键字 ，而后分别每个子序列对Kd-1进行排序，最后将所有子 序列依次联接在一起成为一个有序序列。 2．特点：按MSD进行排序时，必须将序列逐层分割成若干子序列， 然后对各子序列分别进行排序。 ② 最低位优先LSD（Least Signigicant Digit first） 1．算法实现：从最次位关键字Kd-1起进行排序。然后再对高一位的关 键字Kd-2进行排序，依次重复，直至对K0进行排序后便成为一个有序序列。 2．特点： a. 按LSD进行排序时，不必分成子序列，对每个关键字都是整个序列 参加排序，但对Ki(0≤i≤d－2) 进行排序时，只能用稳定的排序方法。

的不同值，后一个关键字Ki+1均取相同值），可通过若干次“分配”和“收集”来 实现排序。 b. 按LSD进行排序时，在一定的条件下（即对前一个关键字Ki(0≤i≤d-2) 的不同值，后一个关键字Ki+1均取相同值），可通过若干次“分配”和“收集”来 实现排序。 （3）例子 例如，已知扑克牌中52张牌面的次序关系为： ♣2<♣3<…<♣A<♦2<♦3<…<♦A<♥2<♥3<…<♥A<♠2<♠3<…<♠A 每一张牌有两个“关键字”：花色(♣<♦<♥<♠)和面值(2<3<…<A)，且“花色”的地 位高于“面值”。 扑克牌整理成如上所述关系时： MSD：先按不同“花色”分成有次序的4堆,每一堆的牌均具有相同的“花色”, 然后分别对每一堆按“面值”大小整理有序。 LSD：先按不同“面值”分成13堆,然后将这13堆牌自小至大叠在一起（“3” 在“2”之上，“4”在“3”之上，……，最上面的是4张“A”），然后将 这付牌整个颠倒过来再重新按不同“花色”分成4堆，最后将这4堆牌 按自小至大的次序合在一起（♣在最下面，♠在最上面）。

￡10.6.2 链式基数排序 （1）定义 有的逻辑关键字可以看成由若干个关键字复合而成的，且每个关键字Kj都 在相同的范围内，则按LSD进行排序时，只要从最低数位关键字起，按关键字 的不同值将序列中记录“分配”到PADIX个队列中后再“收集”之，如此重复d次。 按这种方法实现的排序称之为基数排序。其中“基”指的是RADIX的取值范围。 链式基数排序：用链表作存储结构的基数排序。 例如，若关键字是数值，且其值都在0≤K≤999范围内，则可把每一个十 进制数字看成一个关键字，即可认为K由3个关键字(K0, K1, K2)组成，其中K0是 百位数，K1是十位数，K2是个位数，对每一个关键字0≤Ki≤9（i＝0, 1, 2）， “基”为10。

（2）算法实现 ①数据类型的定义 #define MAX_NUM_OF_KEY 8 //关键字项数的最大值 #define RADIX 10 //关键字基数，此时是十进制整数的基数 #define MAX_SPACE 10000 typedef struct { KeyType keys[MAX_NUM_OF_KEY]; //关键字 InfoType otheritems; //其他数据项 int next; } SLCell; //静态链表的结点类型 SLCell r[MAX_SPACE]; //静态链表的可利用空间，r[0]为头结点 int keynum; //记录的当前关键字个数 int recnum; //静态链表的当前长度 } SLList; //静态链表类型 typedef int ArrType[RADIX]; //指针数组类型

②算法实现 算法10.15为链式基数排序中一趟分配的算法，算法10.16为一趟收集的算法，算法10.17为链式基数排序的算法。 算法10.15如下： void Distribute (SLCell &r, int i, ArrType &f, ArrType &e) { //静态链表L的r域中记录已按(keys[0], … , keys[i－1])有序。本算法按第i //个关键字keys[i]建立RADIX个子表，使同一子表中记录的keys[i]相同。 //f[0..RADIX-1]和e[0..RADIX-1]分别指向各子表中第一个和最后一个记录。 for (j = 0; j < Radix; + + j) //各子表初始化为空表 f[j] = 0; for (p = r[0].next; p; p = r[p].next) { j = ord(r[p].keys[i]); //ord将记录中第i个关键字映射到[0..RADIX-1] if (!f[j]) f[j] = p; else r[e[j]].next = p; e[j] = p; //将p所指的结点插入第j个子表中 } // for } // Distribute

算法10.16如下： void Collect (SLCell &r, int i, ArrType &f, ArrType &e) { //本算法按keys[i]自小至大地将f[0..RADIX－1]所指各子表依次链接成一个链表， //一个链表， e[0..RADIX-1]为各子表的尾指针。 for (j = 0; !f[j]; j = succ(j)); //找第一个非空子表，succ为求后继函数 r[0].next = f[j]; //r[0].next指向第一个非空子表中第一个结点 t = e[j]; while (j < RADIX) { for (j = succ(j); j < RADIX－1 && !f[j]; j = succ(j)); //找下一个非空子表 if (f[j]) { //链接两个非空子表 r[t].next = f[j]; } r[t].next = 0; //t指向最后一个非空子表中的最后一个结点 } // Collect

算法10.17如下： void RadixSort (SLList &L) { //L是采用静态链表表示的顺序表。对L作基数排序，使得L成为 //按关键字自小到大的有序静态链表,L.r[0]为头结点。 for (i = 0; i < L.recnum; + + i) L.r[i].next = i + 1; L.r[L.recnum].next = 0; //将L改造为静态链表 for (i = 0; i < L.keynum; + + i) { //按最低位优先依次对各关键字进行分配和收集 Distributr (L.r, i, f, e); //第i趟分配 Collect(L.r, i, f, e); //第i趟收集 } // for } // RadixSort 从上述算法中容易看出，对于n个记录（假设每个记录含d个关键字，每个关 键字的取值范围为rd个值）进行链式基数排序的时间复杂度为O(d(n + rd))，其中 每一趟分配的时间复杂度为O(n)，每一趟收集的时间复杂度为O(rd)，整个排序需 进行d趟分配和收集。所需辅助空间为2rd个队列指针。

例如，图10.13(a)所示；第一趟分配对最低位关键字（个位数）进行，改变 （3）例子 例如，图10.13(a)所示；第一趟分配对最低位关键字（个位数）进行，改变 记录的指针值将链表中的记录分配至10个链队列中去，每个队列中的记录关键字 的个位数相等，如图10.13(b)所示，其中f[i]和e[i]分别为第i个队列的头指针和尾 指针；第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非 空队列的队头记录，重新将10个队列中的记录链成一个链表，如图10.13(c)所示； 第二趟分配，第二趟收集及第三趟分配和第三趟收集分别是对十位数和百位数进 行的，其过程和个位数相同，如图10.13(d)~(g)所示。至此排序完毕。 278 109 063 930 589 184 505 269 008 083 (a) 初始状态 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 930 063 184 505 278 109 269 589 008 083 (b) 第一趟分配之后

e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 930 063 083 184 505 278 008 109 589 269 (c) 第一趟收集之后 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 505 930 063 278 083 269 589 008 109 184 (d) 第二趟分配之后 505 008 109 930 063 269 278 083 184 589 (e) 第二趟收集之后 返回 说明

e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 008 269 589 063 109 184 930 505 083 278 (f) 第三趟分配之后 008 063 083 109 184 269 278 505 589 930 (g) 第三趟收集之后的有序文件 图10.13 链式基数排序示例 返回 说明

￡10.7 各种内部排序方法的比较讨论 （1）算法比较 综合比较本章内讨论的各种内部排序方法，大致有如下结果： 基数排序 O(d(n+rd)) O(d(n+rd)) O(rd) 排序方法 平均时间 最坏情况 辅助存储 简单排序 O(n2) O(n2) O(1) 快速排序 O(nlogn) O(n2) O(nlogn) 堆排序 O(nlogn) O(nlogn) O(1) 归并排序 O(nlogn) O(nlogn) O(n) 从上表易知，本章讨论的所有排序方法中，没有哪一种是绝对最优的。 在实用时需根据不同情况适当选用，甚至可将多种方法结合起来使用。

（2）地址排序 ①定义 地址排序，即另设一个地址向量指示相应记录，同时在排序过程中 不移动记录而移动地址向量中相应分量的内容。 ②重排算法 重排算法： 从i＝1起依次检查每个分量位置上的记录是否正确到位。 1.若adr[i] = i，则r[i]中恰为第i个最小关键字的记录，该位置上的记 录不需要调整； 2.若adr[i] = k≠i，则说明r[k]中记录是第i个最小关键字的记录，应 在暂存记录r[i]之后将r[k]中记录移至r[i]的位置上。 依次类推，直至找到某个值j = adr[adr[…adr[k]…]],等式adr[j] = i成 立时,将暂存记录移至r[j]的位置上。至此完成一个调整记录位置的小循环。 算法10.18即为上述重排记录的算法。

算法10.18如下： void Rearrange (SqList &L, int adr[ ]) { //adr给出顺序表L的有序次序，即L.r[adr[i]]是第i小的记录。 //本算法按adr重排L.r，使其有序。 for (i = 1; i < L.length; + + i) if (adr[i] != i) { j = i; L.r[0] = L.r[i]; //暂存记录L.r[i] while (adr[j] != i) { //调整L.r[adr[i]]的记录到位直到adr[j]=i为止 k = adr[i]; L.r[j] = L.r[k]; adr[j] = j; j = k; } // while L.r[j] = L.r[0]; adr[j] = j; //记录按序到位 } // if } // Rearrange 返回算 法说明

③ 例子 例如，对图10.14(a)所示记录序列进行地址排序时，可附设向量adr(1:8)。 在开始排序之前令adr[i]:=adr[j]代替，则在排序结束之后，地址向量中的值 指示排序后的记录的次序，r[adr[1]]为关键字最小的记录，r[adr[8]]为关键字 最大的记录，如图10.14(b)所示。 在需要时,可根据adr的值重排记录的物理位置.由于图10.14(b)中adr[1] = 6， 则在暂存R(49)以后,需将R(13)从r[6]的位置移至r[1]的位置。又因为adr[6] = 2， 则应将R(65)从r[2]的位置移至r[6]的位置。同理，将R(27)移至r[2]的位置，此 时，因adr[4] = 1，则R(49)应置入r[4]的位置。完成上述调整后的记录及地址向 量的,状态如图10.14(c)所示。 R(49) R(65) R(38) R(27) R(97) R(13) R(76) R(49) r (1:8) adr (1:8) 1 2 3 4 5 6 7 8 (a) 待排记录和地址向量的初始状态

adr (1:8) 6 4 3 1 8 2 7 5 (b) 排序结束后的地址向量 R(13) R(27) R(38) R(49) R(97) R(65) R(76) R(49) r (1:8) adr (1:8) 1 2 3 4 8 6 7 5 (c) 重排记录过程中的状态 返回 说明 图10.14 地址排序示例 间复杂度为 。 （3）内部排序可能达到的最快速度 经证明，借助于“比较”进行排序的算法在最坏情况下能达到的最好的时