1.4 排序

所谓排序，就是要整理文件中的记录，使之按关键字递增（或递减）次序排列起来。当待排序记录的关键字均不相同时，排序结果是唯一的，否则排序结果不唯一。

在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。

要注意的是，排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。

1.4.1 插入排序

插入排序的基本思想是每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。

1．直接插入排序

直接插入排序的过程为在插入第 i 个记录时， R ₁ ,R ₂ ,… , R _{i –1} 已经排好序，将第 i 个记录的排序码 k _i 依次和 R ₁ , R ₂ ,…, R _{i –1} 的排序码逐个进行比较，找到适当的位置。使用直接插入排序，对于具有 n 个记录的文件，要进行 n –1趟排序。各种状态下的时间复杂度如表1-2所示。

说明 ：初始文件按关键字递增有序，简称“正序”，初始文件按关键字递减有序，简称“反序”。

2．希尔排序

希尔（Shell）排序的基本思想是：先取一个小于 n 的整数 d ₁ 作为第一个增量，把文件的全部记录分成 d ₁ 个组。所有距离为 d _l 的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量 d ₂ ＜ d ₁ 重复上述的分组和排序，直至所取的增量 d _t =1( d _t ＜ d _{t –l} ＜ O ＜ d ₂ ＜ d ₁ )，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

一般取 d ₁ = n /2， d _{i +1} = d _i /2。如果结果为偶数，则加1，保证 d _i 为奇数。

例如我们要对关键码{72，28，51，17，96，62，87，33，45，24}进行排序，这里n=10，首先取d1=n/2=5。则排序过程如图1-15所示。

希尔排序是不稳定的，希尔排序的执行时间依赖于增量序列，其平均时间复杂度为 O ( n ^1.3 )。

1.4.2 选择排序

选择排序的基本思想是每步从待排序的记录中选出排序码最小的记录，顺序存放在已排序的记录序列的后面，直到全部排完。选择排序中主要使用直接选择排序和堆排序。

1．直接选择排序

直接选择排序的过程是，首先在所有记录中选出排序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换……依次类推，直到所有记录排完为止。

无论文件初始状态如何，在第 i 趟排序中选出最小关键字的记录，需做 n – i 次比较，因此，总的比较次数为 n ( n –1)/2= O ( n ² )。当初始文件为正序时，移动次数为1；文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3( n –1)。直接选择排序的平均时间复杂度为 O ( n ² )。直接选择排序是不稳定的。

2．堆排序

堆排序是一种树形选择排序，是对直接选择排序的有效改进。 n 个关键字序列 K _l , K ₂ ,…, K _n 称为堆，当且仅当该序列满足（ K _i ≤ K _2i 且 K _i ≤ K _{2 i +1} ）或（ K _i ≥ K ₂ i且 K _i ≥ K _{2 i +1} ），（1≤ i ≤ ）。 根结点（堆顶）的关键字是堆里所有结点关键字中最小者，称为小根堆；根结点的关键字是堆里所有结点关键字中最大者，称为大根堆。

若将此序列所存储的向量 R [1.. n ]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树，即树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。

堆排序的关键步骤有两个，一是如何建立初始堆；二是当堆的根结点与堆的最后一个结点交换后，如何对少了一个结点后的结点序列做调整，使之重新成为堆。

下面，我们通过一个例子来具体说明建立初始堆和调整堆的过程。假设关键字序列为{42，13，24，91，23，16，05，88}，则第一次建立的二叉树如图1-16（a）所示。

①从 i =[n/2]开始比较父结点和子结点的关系，如果不满足堆的定义，就进行调整。我们假设需要建立大根堆，本题 n =8，所以从第4个元素（91）开始调整。

●　因为91大于其子结点88，所以不需要调整；

●　再看第3个元素（24），同样，因为24大于其子结点16和05，也不需要调整；

●　再看第2个元素（13），13小于其子结点23和91，需要把13和91交换（把父结点与关键值最大的那个子结点交换）。这时，13比其子结点88要小，又需要交换。结果如图1-16（b）所示。

●　再看第1个元素（42），因为42小于其左子结点91，需要交换。

●　这时，42还小于其左子结点88，又需要交换42和88的值。建堆过程结束，所建立的初始堆如图1-17（a）所示。

②在初始堆的基础上，把第一个元素（91）和最后一个元素（13）交换，输出91。这时，如图1-17（b）所示。

③在图1-17（b）的基础上，因13小于其左右子结点88和24，则和88交换，交换后，13还小于其左右子结点42和23，则和42再交换，如图1-18（a）所示。

④图1-18（a）又是一个n–1个元素的堆，把第一个元素（88）和最后一个元素（05）交换，输出88。这时，如图1-18（b）所示。

⑤在图1-18（b）的基础上，因05小于其左右子结点42和24，则和42交换，交换后，05还小于其左右子结点13和23，则和23再交换，如图1-19（a）所示。

⑥图1-19（a）又是一个n–2个元素的堆，把第一个元素（42）和最后一个元素（16）交换，输出42。这时，如图1-19（b）所示。

⑦在图1-19（b）的基础上，因16小于其左右子结点23和24，则和24交换。如图1-20（a）所示。

⑧图1-20（a）又是一个n – 3个元素的堆，把第一个元素（24）和最后一个元素（05）交换，输出24。这时，如图1-20（b）所示。

⑨在图1-20（b）的基础上，因05小于其左右子结点23和16，则和23交换。交换后，05还是小于其子结点13，和13再交换。如图1-21（a）所示。

⑩图1-21（a）又是一个n–4个元素的堆，把第一个元素（23）和最后一个元素（05）交换，输出23。这时，如图1-21（b）所示。

11在图1-21（b）的基础上，因05小于其左右子结点13和16，则和16交换。如图1-22（a）所示。

12图1-22（a）又是一个n – 5个元素的堆，把第一个元素（16）和最后一个元素（05）交换，输出16。这时，如图1-22（b）所示。

13在图1-22（b）的基础上，因05小于其左子结点13，则和13交换，如图1-23（a）所示。

14图1-23（a）又是一个n – 6个元素的堆，把第一个元素（13）和最后一个元素（05）交换，输出13。这时，如图1-23（b）所示，堆排序过程结束。

堆排序的最坏时间复杂度为 O ( n log2 n )，堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为 O (1)，它是不稳定的排序方法。

1.4.3 交换排序

交换排序的基本思想是两两比较待排序记录的排序码，并交换不满足顺序要求的那些偶对，直到满足条件为止。交换排序的主要方法有冒泡排序和快速排序。

1．冒泡排序

冒泡排序将被排序的记录数组 R [1.. n ]垂直排列，每个记录 R [ i ]看做是重量为 k _i 的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组 R ：凡扫描到违反本原则的轻气泡，就使其向上“飘浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

冒泡排序的具体过程如下。

第一步，先比较 k ₁ 和 k ₂ ，若 k ₁ ＞ k ₂ ，则交换 k ₁ 和 k ₂ 所在的记录，否则不交换。继续对 k ₂ 和 k ₃ 重复上述过程，直到处理完 k _{n –1} 和 k _n 。这时最大的排序码记录转到了最后位置，称第1次起泡，共执行 n – 1次比较。

与第一步类似，从 k ₁ 和 k ₂ 开始比较，到 k _{n –2} 和k _{n –1} 为止，共执行 n – 2次比较，称第2次起泡。

依次类推，共做 n –1次起泡，完成整个排序过程。

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数为 n –1次，记录移动次数为0。因此，冒泡排序最好的时间复杂度为 O ( n )。

若初始文件是反序的，需要进行 n – 1趟排序。每趟排序要进行 n – i 次关键字的比较（1≤ i ≤ n – 1），且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较次数达到最大值 n ( n –1)/2= O ( n ² )，移动次数也达到最大值3 n ( n –1)/2= O ( n ² )。因此，冒泡排序的最坏时间复杂度为 O ( n ² )。

虽然冒泡排序不一定要进行 n –1趟，但由于它的记录移动次数较多，故平均时间性能比直接插入排序要差得多。冒泡排序是就地排序，且它是稳定的。

2．快速排序

快速排序采用了一种分治的策略，通常称其为分治法。其基本思想是将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

快速排序的具体过程如下。

第一步，在待排序的 n 个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组，第1组各记录的排序码都小于等于该排序码，第2组各记录的排序码都大于该排序码，并把该记录排在这两组中间。

第二步，采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。

例如我们要对关键码{7，2，5，1，9，6，8，3}进行排序，选择第一个元素为基准。第一趟排序的过程如图1-24所示。

要注意的是，在快速排序中，选定了以第一个元素为基准，接着就拿最后一个元素和第一个元素比较，如果大于第一个元素，则保持不变，再拿倒数第二个元素和基准比较；如果小于基准，则进行交换。交换之后，再从前面的元素开始与基准比较，如果小于基准，则保持不变；如果大于基准，则交换。交换之后，再从后面开始比较，依次类推，前后交叉进行。

然后，再采取同样的办法对{3，2，5，1，6}和{8，9}分别进行排序，具体过程如图1-25所示。

快速排序的时间主要耗费在划分操作上，对长度为 k 的区间进行划分，共需 k –1次关键字的比较。

最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准左边的子区间为空（或右边的子区间为空），而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做 n –1次划分，第 i 次划分开始时区间长度为 n – i +1，所需的比较次数为 n – i （1≤ i ≤ n –1），故总的比较次数达到最大值 n ( n – 1)/2= O ( n ² )。如果按上面给出的划分算法，以每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增序（或递减序）排列时，每次划分所取的基准就是当前无序区中关键字最小（或最大）的记录，则快速排序所需的比较次数反而最多。

在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数 O ( n log ₂ n )。

因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为 O ( n ² )，最好时间复杂度为 O ( n log ₂ n )。

尽管快速排序的最坏时间为 O ( n ² )，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为 O ( n log ₂ n )。快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为 O (log ₂ n )，故递归后需栈空间为 O (log ₂ n )。在最坏情况下，递归树的高度为 O ( n )，所需的栈空间为 O ( n )。快速排序是不稳定的。

1.4.4 归并排序

归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时，把含有 n 个结点的待排序序列看做由 n 个长度都为1的有序子表所组成，将它们依次两两归并得到长度为2的若干有序子表，再对它们两两合并。直到得到长度为 n 的有序表，排序结束。

例如，我们需要对关键码{72，28，51，17，96，62，87，33}进行排序，其归并过程如图1-26所示。

归并排序是一种稳定的排序，可用顺序存储结构，也易于在链表上实现。对长度为 n 的文件，需进行log ₂ n 趟二路归并，每趟归并的时间为 O ( n )，故其时间复杂度无论是在最好情况下还是在最坏情况下均是 O ( n log ₂ n )。归并排序需要一个辅助向量来暂存两个有序子文件归并的结果，故其辅助空间复杂度为 O ( n )，显然它不是就地排序。

1.4.5 基数排序

设单关键字的每个分量的取值范围均是 C ₀ ≤ k _j ≤ C _{rd –1} (0≤ j ＜ rd )，可能的取值个数 rd 称为基数。基数的选择和关键字的分解因关键字的类型而异。

●　若关键字是十进制整数，则按个、十等位进行分解，基数rd=10，C ₀ =0，C ₉ =9，d为最长整数的位数；

●　若关键字是小写的英文字符串，则rd=26，C _o ='a'，C ₂₅ ='z'，d为字符串的最大长度。

基数排序的基本思想是从低位到高位依次对待排序的关键码进行分配和收集，经过 d 趟分配和收集，就可以得到一个有序序列。

基数排序的具体实现过程如下。

设有 r 个队列，队列的编号分别为0,1,2,…, r –1。首先按最低有效位的值把 n 个关键字分配到这 r 个队列中，然后从小到大将各队列中关键字再依次收集起来；接着再按次低有效位的值把刚刚收集起来的关键字分配到 r 个队列中。重复上述收集过程，直至最高有效位，这样便得到一个从小到大的有序序列。为减少记录移动的次数，队列可以采用链式存储分配，称为链式基数排序。每个队列设有两个指针，分别指向队头和队尾。

例如我们需要对{288，371，260，531，287，235，56，299，18，23}进行排序，因为这些数据最高位为百位，所以需要分三趟分配和收集。第一趟分配和收集（按个位数）的过程如图1-27所示。第二趟分配与收集（按十位数）的过程如图1-28所示。第三趟分配与收集（按百位数）的过程如图1-29所示。

基数排序的时间复杂度为 O ( d ( r + n ))，所需的辅助存储空间为 O ( n + rd )，基数排序是稳定的。

1.4.6 算法复杂性比较

在此，我们把常用的排序算法的复杂度进行列表，如表1-3所示。