8.1 基本概念
排序（Sorting）是数据处理中经常使用的一种重要运算。如何进行排序，特别是高效地进行排序是计算机应用中的重要课题之一。
在本章中，我们假定被排序的对象是由一组记录组成的文件，而记录则由若干个数据项（或域）组成，其中有一项可用来标识一个记录，称为关键字项，该数据项的值称为关键字（Key）。关键字可用来作为排序运算的依据，它可以是数学类型，也可以是字符类型，选取记录中的哪一项作为关键字，根据问题的要求而定。例如，在高考成绩统计中将每个考生作为一个记录，它包含准考证号，姓名，语文，外语，物理，化学，生物的分数和总分数等项内容，若要唯一地标识一个考生的记录，则必须用“准考证号”。若要按照考生的总分数排名次，则需要用“总分数”作为关键字。
所谓排序，就是要整理文件中的处理，使得它按关键字递增（或递减）的次序排列起来。也就是说，若给定的文件含有n个记录 R1,R2,„,Rn，它们的关键字分别是k1,k2,„,kn，我们要把n个记录重新排列为Ri1,Ri2,„,Rin，使得ki1≤ki2≤„≤kin(ki1≥ki2≥„≥kin)。
显然，当待排序记录的关键字均不相同时，则排序的结果是唯一的，否则排序的结果不一定唯一。如果待排序的文件中，存在有多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的；反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。
各种排序方法可以按照不同的原则加以分类，在排序过程中，若整个文件都是放在内存中处理，排序时不干涉及数据内、外存交换，则称之为内部（简称内排序）；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。内排序适用于记录个数不很多的小文件，外排序则适用于记录个数太多，不能一次将其全部记录放入内存的大文件。按所用的策略不同，内部排序方法可以分为五类 ：插入排序、选择排序、交换排序、归并排序和分配排序。
每一种内部排序方法均可在不同的存储结构上实现。通常，文件可有下列三种存储结构： （1） 以一维数组作为存储结构，排序过程是对记录本身进行物理重排，即通过比较（2） （3）
和判断，把记录移到合适的位置；
以链表（动态链表或静态链表）作为存储结构，在排序过程中无须移动记录，仅需修改指针即可，通常把这类排序称为表排序；
有的排序方法难于在链表上实现，此时，若需要避免排序过程中记录的移动，可以为建立一个辅助表（例如，包括关键字和指向记录的指针组成的索引表），这样，排序过程中只需对这个辅助的表目进行物理重排，只移动辅助表的表目，而不移动记录本身。
要在繁多的排序方法中，简单地判断哪一种算法好，以便能普遍选用是困难的。评论排序算法好坏的标准主要是两条：第一条是算法执行时所需的时间；第二条是执行算法所需要的附加空间。另外，算法本身的复杂程度也是考虑的一个因素。因为排序算法所需的附加空间一般都不大，矛盾并不突出，而排序是经常执行的一种运算，往往属于系统的核心部分，因此，排序的时间开销是算法的好坏的最重要的标志。排序的时间开销主要是指执行算法中
关键字的比较次数和记录移动的次数，因此，在下面讨论各种内部排序算法时，我们将给出各算法的比较次数及移动次数。
在本章中，除8.8节均是讨论内部排序。若无特别声明，以下均按递增序讨论排序，并且以记录数组作为文件的存储结构。为了简单起见，假设关键字是整数，文件的类型说明如下：
Typedef struct /*定义记录为结构类型*/ { int key; /* 关键字域 */
datatype other; /* 记录的其他域 */ } rectype;
Rectype R[n]; /* R为记录类型的数组 */
其中，n为文件的记录总数加1。
插入排序（Insertion Sort）的基本思想是：每次讲一个待排序的记录，按其关键字大小插入到前面已经排好序的文件中的适当位置，直到全部记录插入完成为止。本节介绍直接插入排序和希尔排序。
8.2 插 入 排 序
8.2.1 直接插入排序
假设待排序的记录存放在数组R[n]中，排序过程的某一中间时刻，R被划分成两个子区间[R[1]，R[i-1]]和[R[i]，R[n-1]]，其中：前一个子区间是已排好序的有序区；后一个子区间则是当前未排序的部分，不妨称其为无序区。直接插入排序的基本操作是将当前无序区的第1个记录R[i]插入到有序区中适当位置，使得R[1]到R[i]变为新的有序区。
初始时，令i=1，因为一个记录自然是有序的，故R[i]自成为一个有序区，无序区则是R[2]到R[n-1]，然后依次将R[2]，R[3]，„，插入到当前的有序区中，直至i=n-1时，将R[n-1]插入到有序区为止。
现在的问题是：如何将一个记录R[i]（i=2，3，„，n-1）插入到当前的有序区，使得插入后仍保证该区间记录是按关键字有序的。显然，最简单的方法是：首先，在当前有序区R[1]到R[i-1]中查找R[i]的正确插入位置k（1≤k≤i-1），然后，将R[k]到R[i-1]中记录均后移一个位置，腾出k位置上的空间插入R[i]。当然，若有R[i]的关键字大于R[1]到R[i-1]中所有记录的关键字，则R[i]就是插入原位置。但是，更为有效的方法是使查找比较操作和记录移动操作交替地进行，具体做法是将待插入记录R[i]的关键字依次与有序区中记录R[j]（j=i-1，i-2，„，1）的关键字进行比较，若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置；若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。因为关键字比R[i]的关键字大的记录均已后移，所以j+1的位置已经腾空，只要将R[i]直接插入此位置即可。下面给出其算法描述：
INSERTSORT(R) /* 对数组R按递增序进行插入排序 */
rectype R[]; /* R[0]是监视哨 */ { int i,j;
for(i=2; i } /* INSERTSORT */ 算法中引进附加记录R[0]有两个作用：其一是进入查找循环之前，它保存了R[i]的副本，使得不至于因记录的后移而丢失R[i]中的内容；其二是在while循环“监视”下标变量j是否越界，一旦越界（即j<1），R[0]自动控制while循环的结束，从而避免了在while循环内的每一次都要检测j是否越界（即省略了循环条件“j≥1”）。因此，我们把R[0]称为“监视哨”，这种技巧，使得测试循环条件的时间大约减少一半，对于记录数较大的文件，节约的时间是相当客观的。希望读者能够掌握这种技巧。 按照上述算法，我们用一例子来说明直接插入排序的过程。设待排序的文件有8个记录，其关键字分别为：49，38，65，97，76，13，27，49’。为了区别两个相同的关键字49，我们在后一个49右上加了一撇以示区别。其排序过程如图8.1所示，图中用括号表示当前的有序区。 直接插入排序算法由两重循环组成，对于有n个记录的文件外循环表示要进行n-1趟插入排序，内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。若初始文件按关键字递增有序（以下简称“正序”），则在每一趟排序中仅需进行一次关键字的比较，此时n-1趟排序总的关键字比较次数取最小值Cmin=n-1；并且在每一趟排序中，无须后移记录。但是，在进入while循环之前，将R[i]保存到监视哨R[0]中需移动一次记录，在该循环结束之后将监视哨中R[i]的副本插入到R[j+1]也需要移动一次记录，此时排序过程总的记录移动此数也取最小值Mmin=2(n-1)。反之，若初始文件按关键字递增有序（以下简称“反序”），则关键字的比较次数和记录移动次数均取最大值。在反序情况下，对于for循环的每一个i值，因为当前有序区R[1]到R[i-1]的关键字均大于待插入记录R[i]的关键字，所以while循环中要进行i次比较才终止，并且有序区中所有的i-1个记录均后移一个位置，再加上while循环前后的两次移动，则移动记录的次数为i-1+2。由此可得排序过程关键字比较总次数的 最大值Cmax和记录移动总次数的最大值Mmax： Cmax==(n+2)(n-1)/2=O(n2) [初始关键字]j=2(38)j=3(65)j=4(97)j=5(76)j=6(13)j=7(27)j=8(49')监视哨R[0][49] 38 65 97 76 13 27 49'[38 49] 65 97 76 13 27 49’[38 49 65] 97 76 13 27 49’[38 49 65 97] 76 13 27 49’[38 49 65 76 97] 13 27 49’[13 38 49 65 76 97] 27 49’[13 27 38 49 65 76 97] 49’[13 27 38 49 49' 65 76 97]图8.1 直接插入排序事例 Mmax==(n-1)(n+4)/2=O(n 2 ) 由上述分析可知，当文件的初始状态不同时，直接插入排序所好肥的时间是有很大差异的。最好情况是文件初始态为正序，此时算法的时间复杂度为O(n)，最坏情况是文件初始态为反序，相应是时间复杂度为O(n2).容易证明，算法的平均时间复杂度也是O(n2)。显然名算法所需的辅助空间是一个监视哨，故空间复杂度S(n)=O(1)。 直接插入法排序是稳定的排序方法。 8.2.2 希 尔 排 序 希尔排序（Shell’s Method）又称“缩小增量排序”（Diminishing Increment）是由D.L.Shell在1959年提出来的。它的作用是：先取定一个小于n的整数d1最为第一个增量，把文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后，取第二个增量d2< d1重复上述分组和排序，直至所取的增量dt=1(dt 第一趟排序时，d1=5，整个文件被分成5组：(R1，R6)，(R2，R7)，„，(R5，R10)各组中的第1个记录都自成一个有序区，我们依次将各组的第2个记录R6，R7，„，R10分别插入到各组的有序区中，使文件的各组均是有序的，其结果见图8.2的第七行。 第二趟排序时，d1=3，整个文件分成：(R1，R4，R7，R10)，(R2，R5，R8)，(R3，R6，R9)，各组的第1个记录仍自成一个有序区，然后依次将各组的第2个记录R4，R5，R6分别插入到该组的当前有序区中，使得(R1，R4)，(R2，R5)，(R3，R6)均变为新的有序区，接着依次将各组的第3个记录R7，R8，R9分别插入到该组的有序区中，又使得(R1，R4，R7)，(R2，R5，R8)，(R3，R6，R9)均变为新的有序区，最后将R10插入到有序区(R1，R4，R7)中就得到第二趟排序结果。 最后一趟排序时，d3=1，即是对整个文件做直接插入排序，其结果即为有序文件。 排序过程如图8.2所示。 初始关键字49 38 65 97 76 13 27 49' 55 04 49 13 38 27 65 49' 97 55 76 04一趟排序结果：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 7604 23 27 38 49' 49 55 65 76 97图8.2 希尔排序事例 若不设置监视哨，根据上例的分析不难写出希尔排序算法，请读者自行完成之。下面我们先分析如何设置监视哨，然后给出具体算法。设某一趟希尔排序的增量为h，则整个文件被分成h组：(R1，Rh+1，R2h+1„)，(R2，Rh+2，R2h+2„)，„，(Rh，R2h，R3h„)，因为各组中记录之间的距离均是h，故第1组至第h租的哨兵位置依次为1-h，2-h，„，0。如果像直接插入排序算法那样，将待插入记录R1(h+1≤i≤n)在查找插入位置之前保存到监视哨中，那么必须先计算Ri属于哪一组，才能决定使用哪个监视哨来保存Ri。为了避免这种计算，我们可以将Ri保存到另一个辅助记录x中，而将所有监视哨R1-h，R2-h，„，R0的关键字，设置为小写文件中的任何关键字即可。因为增量是变化的，所以，各趟排序中所需的监视哨数目也不相同，但是我们可以按最大增量d1来设置监视哨。具体算法描述如下： rectype R[n+d1]; /* R[0]到R[di-1]为d1个监视哨 */ int d[t]; /* d[0]到d[t-1]为增量序列 */ SHELLSORT(R,d) rectype R[ ]; int d[ ]; { int i,j,k,h; rectype temp; int maxint=32767; /* 机器中最大整数 */ for(i=0; i h=d[k]; /* 取本趟增量 */ for(i=h+di; i R[j+h]=temp; /* 插入R[i] */ } k++; }while(h!=1) /* 增量为1排序后终止算法 */ } /* SHELLSORT */ 读者可能看出，当增量h=1时，SHELLSORT算法与INSERTSORT基本一致。 对希尔排序的分析提出了许多困难的数学问题，特别是如何选择增量序列才能产生最好的排序效果，至今没有得到解决。希尔本人最初提出取d1=，di+1=，dt=1，t=；以及di+1=，dt=1，t=。读者可参考knuth所著的《计算机程序设计技巧》第三卷，那里给出希尔排序的平均比较次数和平均移动次数都是n左右。 为什么希尔排序的时间性能优于直接排序插入排序呢？我们知道直接插入排序在文件初始态为正序时所需时间最少，实际上，当文件初始态基本有序时直接排序所需的比较和移动次数均较少。另一面，当n值较少时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n)差别不大。在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数直接减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快，因此，希尔排序在效率上较直接插入排序有较大的改进。 希尔排序是不稳定的。参见图8.2的例子，该例中两个相同关键字49在排序前后的相对次序发生了变化。 21.3 8.3 交 换 排 序 交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。本节介绍两种交换排序：起泡排序和快速排序。 8.3.1 起泡排序 设想被排序的记录数组R[0]到R[n-1]垂直竖立，将每个记录R[i]看作是重量为R[i].key的起泡。根据轻气泡不能在重气泡之下的原则，从上往下扫描数组R，凡扫描到违反原则的轻气泡，就使其向上“漂浮”，如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。 初始时，R[0]到R[n-1]为无序区，第一趟扫描从该区底部向上依次比较相邻两个气泡重量，若发现轻者在下，重者在上，则交换两者的位置。本趟扫描完毕时，“最轻”的气泡就漂浮到顶上面，即关键字最小的记录被放在最高位置R[0]上。第二趟扫描时，只需扫视R[1]到R[n-1]，扫描完毕时，“次轻”的气泡漂浮到R[1]的位置上。一般地，第i趟扫描时，R[0]到R[i-1]和R[i]到R[n-1]分别为当前的有序区和无序区，扫描仍是从无序区底部向上直至该区顶部，扫描完毕时，该区中最轻气泡漂浮到顶部位置R[i]上，结果是R[0]到R[i]变为新的有序区。图8.3是起泡排序过程的示例，第1列为初始关键字，第2列起依次为各趟排序（即 各趟扫描）结果，图中用方括号表示待排序的无序区。 因为每一趟排序都使有序区增加一个气泡，在经过n-1趟排序之后，有序区中就有n-1个气泡，而无序区中气泡的重量总是大于等于有序区中气泡的重量，所以，整个起泡排序过程至多需要进行n-1趟排序。但是，若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满轻者在上，重者在下的原则，因此，起泡排序过程可在此趟排序后终止。在图8.3的示例中，在第四趟（图中第5例）排序过程中就没有起泡交换位置，此时整个文件已达到有序状态。为此，在下面给出的算法中，我们引入一个布尔量noswap，在每趟排序之前，先将 13 76 97 65 65 65 65 6527 27 76 97 76 76 76 7649' 49' 49' 76 97 97 97 9749 13 13 13 13 13 13 1338 49 27 27 27 27 27 2765 38 49 38 38 38 38 3897 65 38 49 49 49 49 4976 97 65 49' 49' 49' 49' 49'图8.3 从下往上扫描的起泡排序示例它置为TRUE。当一趟排序结束时，我们再检查noswap，若未曾交换过记录便终止算法。 BUBBLESORT(R) /* 从下往上扫描的起泡排序 */ rectype R[ ]; { int i,j,noswep; rectype temp; for(i=0; i } /* BUBBLESORT */ 容易看出，若文件的初始状态是正序，则一趟扫描就可完成排序，关键字的比较次数为n-1，且没有记录移动。也就是说，起泡排序在最好情况下，时间复杂度是O(n)。若初始文件是反序的，则需要进行n-1趟排序，每趟排序要进行n-1次关键字的比较(0≤i≤n-2)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较移动次数均达到最大值： Cmax==n(n-1)/2=O(n2) Mmax==3n(n-1)/2=O(n2) 因此，起泡排序的最坏时间复杂度为O(n)。它的平均时间复杂度也是O(n)。显然，起泡排序是稳定的。 上述起泡排序算法还可以作如下的改进： （1） 在每趟扫描中，记住最后一次交换发生的位置k，因为该位置之前的相邻记录 都已排了序，所以下一趟扫描可以终止于位置k，而不必进行到预定的下界i。 （2） 上面曾提到文件初始态为正序时只需做一趟扫描，而文件初始态为反序时需做n-1趟扫描。实际上，如果只有最轻的气泡位于R[n-1]的位置，其余的气泡均 已排好序，那么也只需一趟扫描就可以完成排序。例如，对初始关键字序列12，18，42，44，45，67，94，10就仅需一趟扫描；而当只有最重的气泡位于R[0]的位置，其余的气泡均已排好序时，则仍需做n-1趟扫描才能完成排序，例如，对初始关键字序列：94，10，12，18，42，44，45，67就需七趟扫描。造成这种不对称性的原因是，每趟扫描仅能使最重气泡“下沉”一个位置，因此，使位于顶端的最重气泡下沉到底部时，需做n-1趟扫描。如果我们改变扫描方向。使每趟排序均从上到下进行扫描，则情况正好相反，即每趟从上到下的扫描，都能时当前无序区中最重的气泡沉到该区的底部，而最轻气泡均能“上浮”一个位置。因此，对于序列：12，18，42，44，45，67，94，10就必须从上到下扫描七趟才能完成排序，而对序列：94，10，12，18，42，45，67只需从上到下扫描就可完成排序，为了改变上述两种情况下的不对称性，我们可以在排序过程中交替改变扫描方向，具体算法算法则留做习题，请读者自己写出来。 22 8.3.2 快速排序 快速排序（Quick Sort）又称划分交换排序。其基本思想是：在当前无序区R[l]到R[h]中任取一个记录作为比较的“基准”（不妨记为temp），用此基准将当前无序区划分为左右两个较小的无序子区：R[l]到R[i-l]和R[i+l]到R[h]，且左边的无序子区中记录的关键字均小于或等于基准temp的关键字，右边的无序子区中记录的关键字均大于或等于基准temp的关键字，而基准temp则位于最终排序的位置上，即： R[l]到R[i-l]中关键字temp.keyR[i+l]到R[h]的关键字（lih） 当R[l]到R[i-l]和R[i+l]到R[h]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中记录均已排好序为止。 要完成对当前无序区R[l]到R[h]的划分，具体做法是：设置两个指针i和j，它们的初值分别为i=l和j=h。不妨取基准为无序区的第l个记录R[i]（即R[l]），并将它保存在变量temp中。令j自h起向左向左扫描，直到找到第l个关键字小于temp.key的记录R[j]，将R[j]移至i所指的位置上（这相当于交换了R[j]和基准R[i]（即temp）的位置，使关键字小于基准关键字的记录移到了基准的左边）；然后，令i自i+l起向右扫描，直至找到第l个关键字大于temp.key的记录R[i]，将R[i]移至j指的位置上（这相当于交换了R[i]和基准R[j]（即temp）的位置，使关键字大于基准关键字的记录移到了基准的右边）；接着，令j自j-l起向左扫描，如此交替改变扫描方向，从两端各自往中间靠拢，直至i=j时，i便是基准x的最终位置，将x放在此位置上就完成了一次划分。 综合上面的叙述，下面分别给出一次划分及其排序的算法。 int PARTITION(R,l,h) /* 返回划分后被定位的基准记录的位置 */ { QUICKSORT(R,sl,tl) /*对R[sl]到R[t1]快速排序 */ rectype[]; int sl,tl; { int i; if(sl } } /* QUCIKSORT */ int i,j; rectype temp; i=1; j=h; temp=R[i]; /* 初始化，temp为基准 */ do{ while((R[j].key>=temp.key) && (i } while(i != j); R[i]=temp; /*基准temp已被最后定位*/ return i; } /* PARTITION */ 注意：对整个文件R[0]到R[n-1]排序，只需调用QUICKSORT（R，0，n-1）即可。 图 8.4展示了一次划分的过程及整个快速排序的过程。图中方括号表示无序区，方框表示基准temp的关键字，它未参加真正的交换，只交在划分完成时才将它放入正确的位置上。 现在对快速排序的性能做具体分析。 最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准左边的无序子区为空（或右边的无序子区为空），而划分所得的另一个非空的无序子区中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做n-1趟中需进行n-i次比较，故总的比数次数到达到最大值： n1 Cmax(n1)n(n1)/2O(ni12) 显然，如果按上面给出划分算法，每次取当前无序区的第l个记录为基准，那么当文件的记录已按递增序（或递减序）排序时，每次划分所取的基准就是当前无序区中关键字最小（或 最大）的记录，则快速排序所需的比较次数反而最多。 在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基 准的左、右两个无序子区的长度大致相等。设C(n)表示对长度为n的文件进行快速排序所需的比较次数，显然，它应该等于长度为n的无序区进行划分所需的比较次数n-1。加上递归地对划分所得的左、右两个无序子区（长度n/2）进行快速排序所需的比较次数。假设文件长度n=2，那么总的比较次数为： C(n)n2C(n/2)n2[n/22C(n/2)]2n4C(n/2)22k 2n4[n/42C(n/2)]3n8C(n/2)kn33 2O(nlogkC(n/2)nlognnC(1)222n)注意：式中C(1)为一常数，k=logn。 2因为快速排序的记录移动次数不大于比较的次数，所以，快速排序的最坏时间复杂度应为O(n)，最好时间复杂度为O(nlogn)。为了改善最坏情况下的时间性能，可采用“三 22者取中”的规则，即在每一趟划分开始前，首先比较R[l].key，R[h].key和R[(lh)/2].key，令三者中取中值的记录和R[l]交换之。 可以证明：快速排序的平均时间复杂度也是O(nlogn)，它是目前基于比较的内部排 2序方法中速度最快的，快速排序亦因此而得名。 快速排序需要一个栈空间来实现递归。若每次划分均能将文件均匀分割为两部分。则栈的最大深度为 logn1，所需栈空间为O(log22n)。最坏情况，递归深度为n，所需栈 空间为O(n)。 快速排序是不稳定的，请读者自行检验反例：2，2'，1。 8.4 选择排序 选择排序（Selection Sort）的基本方法是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。本节我们介绍两种选择排序：直接选择排序和堆排序。 8.4.1 直接选择排序 直接选择排序（Straight Selection Sort）的基本思想是：第一趟排序是在无序区R[0]到 R[n-1]中选出最小的记录，将它与R[0]交换；第二趟排序是无序区R[l]到R[n-l]中选关键字最小的记录，将它与R[l]交换；而第i趟排序时R[0]到R[i-2]已是有序区，在当前的无序区R[i-l]到R[n-l]中选出关键字最小的记录R[k]，将它与无序区中第l个记录R[i-l]交换，使R[l]到R[i-l]变为新的有序区。因为每趟排序都使有序区中增加了一个记录，且有序区中的记录关键字不大于无序区中记录的关键字，所以，进行n-1趟排序后。整个文件就是递增有序的，直接选择排序的过程如图8.5所示，图中方括号表示无序区。 直接选择排序的具体算法如下： SELECTSORT(R) /*对R[0]到R[n-1]进行直接选择排序*/ rectype[]; { int i,j,k; rectype temp; for(i=0;i 显然，无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需做n-1次比较，因此，总的比较次数为： n1 i1(n1)n(n1)/2O(n) 2至于记录移动次数，当初始文件为正序时，移动次数为0；文件初态为反序时，每趟排序均要执行交换操作，所以，总的移动次数取最大值3(n-1)。直接选择排序的平均时间复杂度为O(n)。 直接选择排序是不稳定的，请读者自行检验反例：2，2'，1。 28.4.2 堆 排 序 上一小节介绍的直接选择排序中，为了从R[1]到R[n]选出关键字最小的记录，必须进行n-1次比较，然后在R[2]到R[n]选出关键字最小的记录，有需要做n-2次比较，事实上，后面这n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较的结果，所以，后一趟排序时又重复执行了这些比较操作。本节介绍的堆排序可以克服这一缺点。 堆排序(Heap Sort)是一树形选择排序，它的特点是，在排序过程中，将R[1]到R[n]看成是一棵完全二叉树顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系（参见6.2.3）来选择关键字最小记录。 首先，引出堆的定义，n个关键字序列K1，K2，„，Kn称为堆，而且仅当该序列满足特性： Ki≤K2i 和 Ki≤K2i+1 (1≤i≤n/2) 从堆的定义可以看出，堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均小于等于它的孩子结点的关键字。例如，关键字序列：10，15，56，30，70就是一个堆，它所对的完全二叉树如图8.6所示。显然，这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若将上面堆定义中的不等号反向，也就是说，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子结点的关键字，则称之为大根堆，大根堆的堆顶关键字最大，其例子参见8.7。显然，在堆中任一棵树亦是堆。 10701556101556253070563070563025151025（a）3070逻辑结构（b）存储结构25（a）1510逻辑结构（b）存储结构图8.6 小根堆示例图8.7 大根堆示例堆排序正事利用小根堆（或大根堆）来选取当前无序区中关键字最小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐渐向前扩大到整个记录区的。 堆排序的第一趟排序首先需“建堆”，即把整个记录数组R[1]到R[n调整为一个大根堆，所以，必须把完全二叉树中以每一结点为跟的子树都调整为堆。显然只有一个结点的树是堆， 而在完全二叉树中，所有序列i>的结点都是叶子，因此，以这些结点为根的子树均已是堆。这样，我们只需依次将以序列号为，-1，„，1的结点作为根的子树都调整为堆即可。按该次序调整每个结点时，其左、右子树均已是堆（不妨将空树看作是堆）。 现在的问题是，若已知结点R[i]的左右子树均已是堆，如何将以R[i]为根的完全二叉树也调整为堆？解决这一问题可采用“筛选法”。筛选法的基本思想是：因为R[i]的左、右子树已是堆，这两棵树的根分别是各自子树中关键字最大特点，所以，我们必须在R[i]和它的左、右孩子中选取关键字最大的结点放到R[i]的位置上。若R[i]的关键字已是三者中的最大者，则无须做任何调整，以R[i]为根的子树已构成堆；否则，必须将R[i]和具有最大关键字的左孩子R[2i]或R[2i+1]进行交换。不妨设R[2i]的关键组最大，将R[i]和R[2i]交换位置，交换之后有可能导致以R[2i+1]为根的子树不再是堆，但由于R[2i]的左、右子树仍然是堆，于是可重复上述过程，将以R[2i]为根的子树调整为堆，„，如此下去，而将最大关键字一层层地选择上来。 图8.8阐明了对于关键字序列：42，13，91，23，16，05，88在建堆过程中完全二叉树及其存储结构的变化情况，其中n=8，故从第4个结点起进行调整。 42132388241691052388132442911605142213391423524616705888142213391488524616705823(a) i=4,23筛下一层（b） i=3,不调整4213138823241691051323882442911605142213391488524616705823142288391423524616705813（c） i=2,13筛下两层9188231324164205（d） i=1,42筛下一层191288342423524616705813（e） 建成的堆图8.8 建堆过程示例下面给出筛选算法： SIFT(R,i,m) /* 在数组R[i]到R[m]中，调整R[i] */ rectype R[ ]; /* 以R[i]为根的完全二叉树构成堆 */ int i,m; { int j; rectype temp; temp=R[i]; j=2*i; while(j<=m) /* jm,R[2*i]是R[i]的左孩子 */ { if((j R[i]=temp; /* 最初被调整结点放入正确位置 */ } /* SEFT */ 在完全二叉树中，若一个结点没有左孩子，则该结点必是叶子，因此，筛选算法中循环条件j≤m不成立时，则表示当前调整结点R[i]是叶子，故筛选过程可以结束。在筛选过程中，若当前被调整结点R[i]和它的左、右孩子结点相比，某一孩子R[j]的关键字最大，则需要交换R[i]和R[j]的位置，将R[i]筛选至下一层，但由于R[i]还可能会被逐层筛下去，为了减少记录移动次数，故算法在筛选开始前将最初被调整的艮结点R[i]保存在temp中，当发生交换时，仅需将R[j]放入其双亲结点R[i]的位置上，而R[i未直接放入R[j]的位置上，只有当整个筛选过程结束时，才讲保存在temp中的记录放到最重的位置上。 有了上述筛选算法，则将最初是的无序区R[1]到R[n]建成一个大根堆，可用一下语句实现： for(i=n/2; i>=1; i--) SIFT(R,i,n); 由于建堆的结果是把R[1]到R[n]中关键字最大的记录选到堆顶R[1]的位置上，排序后这个关键字最大的记录应该是记录区R[1]到R[n]的最后一个记录，因此，将R[1]和R[n]交换后便得到了第一趟排序的结果。 第二趟排序的操作首先是，将当前无序区R[1]到R[n-1]调整为堆。因为第一趟排序后，R[1]到R[n]中只有R[1]的值发生了变化，它的左、右孩子仍然是堆，所以，我们可以调用SIFT(R，1，n-1)麻将R[1]到R[n-1]调整为大根堆，即选出R[1]到R[n-1]中最大关键字放入堆顶。然后，将堆顶记录R[1]和当前无序区的最后一个记录R[n-1]相交换，其结果是R[1]到R[n-2]变为新的无序区，R[n-1]到R[n]为有序区，且有序区中记录的关键字均大于等于无序区中记录的关键字。如此重复n-1趟排序之后，就使有序区扩充到整个记录区R[1]到R[n]。图8.9是堆排序的全过程示例，其中方括号里面的记录是当前的无序区。 堆排序算法如下： HEAPSORT (R) /* 对R[l]到R[n]进行堆排序 */ rectype R[]; { int i; rectype temp; for(i=n/2;i>=1;i--) /*建初使堆*/ SIFT(R,i,n); for(i=n;i>=1;i--) { temp=R[1]; /*当前堆顶记录和最后一个记录交换*/ R[1]=R[i]; R[i]=temp; SIFT(R,1,i-1); /*R[l]到[i-l]重建成堆 */ } } /*HEAPSORT*/ 堆排序的时间，主要由建立初始堆和不断重建这两部分的时间开销构成。建立初始堆共调用了SIFT过程(n/2)次，每次均是将R[i]为根n/2i1的子树调整为堆。显然，具有n个结点的完全二叉树深度是hlogn1,故结点R[i](n/2i1)的层 2数只可能是h-1，h-2，„„，1。由于第l层上的结点个数至多为2l1，故以它们为根 的子树深度为h-l-1。而SIFT算法对深度为k完全二叉树所进行的关键字比较次数，至多为2(k-1)次，因此，建初始堆调用SIFT算法所进行的关键字比较的总次数，不超过C1(n)，且它满足下式： 11C1(n)ih12h1hi12(h1)h2ih123i(h1) 222222h332(h1)h1(1/22/23/2(h1)/2222(n)1log2) 2h4nO(n)第j次重建堆时，堆中有n-j个结点，完全二叉树深度为重建堆所需的比较次数至多为2较总次数不超过C2(n)，且 log2(nj)1，调用SIFT log2(nj)。因此，n-1趟排序过程中重建堆的比 C2(n)2(log(n1)log(n2)log2) 2nlognO(nlogn)22222在SIFT算法中，记录移动次数不会超过比较次数，因此，堆排序的时间复杂度是O(nnlogn)O(nlogn)。 22由于建初始堆所需的比较次数较多，所以，堆排序不适宜于记录数较少的文件。堆排序是我们介绍的第一个最坏时间复杂度O(nlogn)的排序算法，辅助存储空间仅为用于 2交换的记录空间。 堆排序是不稳定的，请读者自己举出反例。 8.5 归并排序 归并排序（Merge Sort）是利用“归并”技术进行排序，所谓归并是指将若干个已排序的子文件合并一个有序的文件。 最简单的归并是将两个有序的子文件合并成一个有序的文件，假设R（low）到R[m]和R[m+1]到R[high]是存储在同一个数组中且相邻的两个有序的子文件，要将它们合并为一个有序文件R1[low]到R1[high]，只要设置三个指示器i、j和k，其初值分别是这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字，取关键字较小的记录的复制到R1[k]中，然后，将指向被复制记录的指示器加1和指向复制位置的指示器k加1，重复这一过程，直至全部记录被复制到R1[low]到R1[high]中为止。其算法如下： MERGR(R,R1,low,mid,high) /*R[low]到R[mid]与R[mid+1]到R[high]是两个有序文件*/ rectype R[],R1[]; /*结果为一个有序文件在R1[low]到R1[high]中*/ int low, mid, high; { int i, j, k; i=low; j=mid+1; k=low; while((i<=mid) && (j<=high)) if(R[i].key<=R[j].key) /*取小者复制*/ R1[k++]=R[i++]; R1[k++]=R[j++]; else while(i<=mid) R1[k++]=R[i++] ; /*复制第一个文件的剩余记录*/ while(j<=high) R1[k++]=R[j++]; /*复制第二个文件的剩余记录*/ } /* MERGE */ 归并排序是利用上述归并操作实现排序的，其基本思想是：将待排序文件R[0]到R[n-1]看成n个长度为1的有序子文件，把这些子文件两两归并，便得到n/2个有序的子文件（当n为奇数时，归并后仍有一个长度为1的子文件）；然后，再把这n/2个有序的子文件两两归并，如此反复，直到最后得到一个长度为n的有序文件为止。上述的每次归并操作，都是将两个子文件合并成一个子文件，这种方法称为“二路归并排序”。类似地也可以有“三路归并排序”或“多路归并排序”。二路归并排序的全过程，如图8.10所示。 在给出二路归并排序算法之前，必须先解决一趟归并问题。在一趟归并中，设各子文件长度为length（最后一个子文件长度可能小于length），则归并前R[0]到R[n-1]中共有 n/length个有序的子文件：R[0]到R[length-1]，R[length]到R[2*length-1]，„ R[(n/length-1)*length]到R[n-1]，调用归并操作将相邻的一对子文件进行归并时，必须对子文件的个数可能是奇数、以及最后一个子文件的长度小于length，这两种特殊情况进行特殊处理。具体算法如下： MERGPASS(R,R1,length) /*对R做一趟归并，结果放在R1中*/ rectype R[ ],R1[ ]; int length; /*length是本趟归并的有序子文件的长度 */ { int i,j; i=0; /*i指向第一对子文件的起始点 */ while(i+2*length-1< n) /*归并长度为length的两个子文件 */ { MERGE(R,R1,i,i+length-1,i+2length-1); i=i+2*length; /*i指向下一对子文件起始点*/ } if(i+length-1 } /*MERGEPASS */ 二路归并排序就是调用“一趟归并”过程，将待排序文件进行若干趟归并，每趟归并后有序子文件的长度length扩大一倍。第一趟归并时，有序子文件的长度length为1，当有序段长度lengthn时排序完成。二路归并算法如下： MERGESORT(R) /*对R进行二路归并排序，结果仍在R中*/ rectype R[ ]; { int length; length=1; while(length MERGEPASS(R1,R,length); /*再次归并，结果在R中 */ length=2*length; } } /*MERGESORT*/ 在上述算法中，第二个调用语句MERGEPASS前并未判断lengthn是否成立，若成立，则排序已完成，但必须把结果从R1复制到R中。而当lengthn时，执行MERGEPASS(R1， R，length)的结果正好是将R1中唯一的有序文件复制到R中。 显然，第i趟归并后，有序子文件长度为2，因此，对于具有n个记录的文件排序，必须做 ilogn 趟归并，每趟归并所花的时间是O(n)，所以，二路归并排序算法的时 22间复杂度为O(nlogn)。算法中辅助数组R1所需的空间是O(n)。 二路归并排序是稳定的。 8.6 内部排序方法的比较选择 迄今为止，已有的排序方法远远不止本章讨论的这些方法，人们之所以热衷于研究多种排序方法，不仅是由于排序在计算机中所处的重要地位，而且还因为不同的方法各有其优缺点，可适用于不同的场合。选取排序方法时需要考虑的因素有：(1)待排序的记录数目n；(2)记录本身信息量的大小；(3)关键字的结构及其分布情况；(4)对排序稳定性的要求；(5)语言工具的条件，辅助空间的大小等。依据这些因素，可得出如下几点结论： （1）若较小（譬如n<50），可采用直接插入排序或直接选择排序。由于直接插入排序所需移动操作较直接选择排序多，因此记录本身信息量较大，则选用直接选择排序为宜。 （2）若文件的初始状态已是按关键字基本有序，则选用直接插入排序或者起泡排序为宜。 （3）若n较大，则应采用时间复杂度为O()的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间复杂度最短；但堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的，若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后，再两两归并之。因为直接插入排序是稳定的，所以，改进后的归并排序仍是稳定的。 （4）在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此，可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于“比较”的排序算法，至少需要O(n)的时间。由于箱排序和基数排序只需一步就会引起m中可能的转移，即把一个记录装入m个箱子之一，因此，在一般情况下，箱排序和基数排序可能在O(n)时间内可完成对n个记录的排序。但遗憾的是，箱排序和基数排序只适用于像字符串和整数这类有明显结构特征的关键字，而当关键字的取值范围属于某个无穷集合（例如实数型关键字）时，无法使用箱排序和基数排序，这时只有借助“比较”的方法来排序。由此可知，若n很大，记录的关键字位数较少且可以分解时，采用基数排序比较好。 （5）前面讨论的排序算法，除基数排序外，都是在一维数组上实现的。当记录本身信息量较大时，为避免好肥大量时间移动记录，可以用链表作为存储结构。譬如插入排序和归并排序都易于在链表上实现，并分别称之为表插入和表归并。但有的排序方法，如快速排序和堆排序，在链表上却难于实现，在这种情况下，可以提取关键字建立索引表，然后，对索引表进行排序。然而，更为简单的方法是：引入一个整型向量t[n]作为辅助表，排序钱，令 t[i]=i(0≤i≤n)；若排序算法中要求交换R[i]和R[j]即可，排序结束后，向量t[n]就指示了记录之间的顺序关系： R[t[o]].key≤R[t[1]].key≤„≤R[t[n-1]].key 无论是用链表，还是用辅助表来实现排序，都有可能要求最重结果是： R[0].key≤R[1].key≤„≤R[n-1].key 若有上述要求，则可以在排序结束后，再按链表或辅助表所规定的次序重排个记录，完成重排的时间是O(n)。 小结 排序是数据处理中经常运用的一种重要运算。首先，我们介绍了排序的概念和有关知识。接着对插入排序、交换排序、选择排序、归并排序个分配排序等五类内部排序方法进行了讨论，分别介绍了各种排序方法的基本思想、排序过程和实现算法，简要地分析了各种算法的时间复杂度和空间复杂度，在对比各种排序方法的基础上，提出供读者选择的参考建议。最后，对外部排序作了简单介绍。 由于排序运算在计算机应用中所处的重要地位，建议读者深刻理解各种内部排序法的基本思想和特点。熟悉内部排序法的排序过程，记住各种算法的时间复杂度分析结果及其分析方法，以便在实际应用中，根据实际问题的要求，选用合适的排序方法。 因篇幅问题不能全部显示，请点此查看更多更全内容