数据结构与算法 课件 第9章 排序

9.1排序的基本概念

9.2插入排序

9.3交换排序

9.4选择排序

9.5归并排序

9.6基数排序

9.7各种内部排序算法的比较和选择9.1排序的基本概念排序可以定义如下：假设序列包含n个记录{R1,R2,…,Rn}，其对应的关键字值序列为{k1,k2,…,kn}，根据1,2,…,n的一种排列p1,p2,…,pn将这n个记录重排为有序序列{Rp1,Rp2,…,Rpn}，使其满足kp1≤kp2≤…≤kpn(或kp1≥kp2≥…≥kpn)。上述定义中，如果ki是主关键字，则排序结果是唯一的；如果ki是次关键字，则两个关键字值可能相等，此时排序结果就不是唯一的。假设记录Ri和Rj的关键字ki=kj，如果在原始序列中，Ri排在Rj之前，而排序后的序列中Ri仍然排在Rj之前，就称此排序是稳定的；反之，如果排序后变成Ri排在Rj之后，就称此排序是不稳定的。根据排序过程涉及存储器的不同，可将排序分为内部排序和外部排序。内部排序是指整个排序过程都在内存中进行的排序；外部排序是指待排序记录的数量很大，在排序过程中，除使用内存外，还需对外存进行访问。显然，内部排序适用于记录个数较少的序列；外部排序则适用于记录个数太多，需同时使用内存和外存的长序列。根据不同算法所用的策略，内部排序可分为插入排序、选择排序、交换排序、归并排序及基数排序等几大类。每一种算法各有优缺点，适合于不同的应用场合，因此要想简单地评价哪种算法最好且能够普遍适用是很困难的。判断排序算法好坏的标准主要有两条：①算法执行所需要的时间；②算法执行所需要的附加空间。另外要考虑的一个因素是算法本身的复杂程度。排序算法所需的附加空间量一般都不大，所以时间复杂度是衡量算法好坏最重要的标志。排序所需的时间主要是指算法执行中关键字的比较次数和记录的移动次数，后面的章节将会对此进行详细讨论。待排序的记录有下列三种存储结构：(1)以一组连续的地址单元(如一维数组)作为存储结构，待排序记录的次序由其物理位置决定。排序过程必须移动记录，进行物理位置上的重排，即通过比较和判定，把记录移到合适的位置。(2)以链表作为存储结构，记录之间的次序由指针决定。因此，排序过程仅需修改指针。(3)待排序记录存储在一组连续的地址单元内，此时若要避免排序过程中记录的移动，可以为该序列建立一个辅助表(如索引表)，在排序过程中只需对这个辅助的表目进行物理重排，而不移动记录本身。待排序记录的数据类型说明如下：9.2插入排序9.2.1直接插入排序直接插入排序(StraightInsertionSort)是一种最简单的排序方法，其基本思路是把关键字ki依次与有序区的关键字ki-1,ki-2,…,k1进行比较，找到应该插入的位置，然后将ki插入。给定待排序的记录序列为R[1]～R[n]，则初始有序区为{R[1]}，直接插入排序可以从i = 2开始，如算法9.1所示。算法9.1中的基本操作是关键字比较和记录移动。记录R[1]作为最初的有序区，从i = 2开始不断将待插入记录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[0]预先对记录R[i]进行备份，使得在后移关键字比R[i]大的记录时不致丢失R[i]中的内容。R[0]在while循环中还可以作为“监视哨”，防止下标变量j越界。由于避免了每次while循环都要检测j是否越界，测试循环条件的时间可以减少约一半。算法9.1直接插入排序。根据算法9.1对待排序的一组记录进行排序，记录的关键字分别为49、31、63、85、75、15、26、49，直接插入排序过程如图9.1所示。直接插入排序的算法9.1非常简洁，容易实现，下面来分析它的效率。从时间上看，整个排序过程只有比较关键字和移动记录两种运算。算法中的外循环表示要进行n-1趟插入排序，内循环的次数则取决于待排序关键字与有序区中i个关键字的关系。可以按两种情况来考虑。当一组记录为正序时(这里按递增有序)，每趟排序的关键字比较次数为1，记录移动次数是2次，即总的比较次数Cmin = n-1，总的移动次数Mmin=2(n-1)；当文件逆序时，要插入的第i个记录均要与前i-1个记录及“监视哨”的关键字进行比较，即每趟要进行i次比较；从记录移动的次数来说，每趟排序中除了上面提到的两次移动外，还需将关键字大于R[i]的记录后移一个位置。这时关键字的比较次数和记录的移动次数均取最大值，总的比较次数和记录的移动次数分别为综上可知，记录关键字的分布对算法执行过程中的时间消耗是有影响的。若在随机情况下，即关键字各种排列出现的概率相同，则可取上述两种情况的平均值作为比较和记录移动的平均次数，约为n2/4。由此，直接插入排序的时间复杂度为O(n2)。从空间上看，直接插入排序只需要一个记录的辅助空间R[0]，空间复杂度为O(1)。直接插入排序是稳定的排序方法。9.2.2希尔排序希尔排序(Shell’sSort)又称为缩小增量排序(DiminishingIncrementSort)，是一种改进的插入排序方法。该方法是D.L.Shell于1959年提出的，故用他的名字命名。我们知道直接插入排序算法的平均时间复杂度为O(n2)，但是由于其算法简单，因此当n较小时效率较高。另外，当一组记录有序时其算法复杂度可以达到最优，即O(n)。希尔排序正是基于这两点对直接插入排序进行改进的。希尔排序的基本思想是：设置t个整数增量(d1 > d2 > … > dt-1 > dt)，其中d1 < n，dt=1；首先以d1为增量，将所有距离为d1倍数的记录放在同一组中，可以得到d1个组，在各组内进行直接插入排序；然后取第二个增量d2，重复上述的分组和排序，直至增量dt=1。设置增量序列时，要使得增量值没有除1之外的公因子，而且最后一个增量值必须为1。下面先看一个具体例子。设待排序文件共有10个记录，其关键字分别为49、31、63、85、75、15、26、49、53、03，增量序列取值依次为5、3、1，排序过程如图9.2所示。由图9.2可见，希尔排序的每一趟就是直接插入排序。增量越大，则得到的子序列越短，此时直接插入排序效率很高；而当增量逐渐减小时，序列已逐渐有序，因此直接插入排序仍然很有效。当增量为1时，所有的记录已经基本有序，并放在同一组中进行直接插入排序。由此，希尔排序的速度较直接插入排序有较大的提高。希尔排序的具体算法如算法9.2所示。算法9.2中没有设置“监视哨”，单元R[0]仅作为暂存单元，所以在内循环(while循环)中增加了一个循环判定条件“j>0”，以防下标越界。当搜索位置j≤0或者R[0].key≥R[j].key时，表示插入位置已找到。为了便于对希尔排序算法的理解，我们用伪代码来描述算法。9.3交换排序9.3.1起泡排序起泡排序(BubbleSort)是最为人们所熟知的交换排序方法。它的过程非常简单，将关键字序列看作是从上到下纵向排列的，按照自下而上的扫描方向对两两相邻的关键字进行比较，若为逆序(即kj1>kj)，则将两个记录交换位置；重复上述扫描排序过程，直至没有记录需要交换为止。第一趟扫描后，关键字最小的记录将上升到第一个记录的位置上；第二趟对后面的n-1个记录进行同样操作，把次小关键字的记录安排在第二个记录的位置上；重复上述过程，分析可知在第n-1趟后，全部记录都按关键字由小到大的顺序排列完毕。在每一趟排序过程中，关键字最小的记录通过比较和交换，会像气泡一样上浮至顶；而关键字较大的记录则逐渐下沉，“起泡排序”的名称由此而得。起泡排序的过程如图9.3所示。对任一组记录进行起泡排序时，至多需要进行n-1趟排序。但是，如果在排序过程中的某一趟扫描后，例如图9.3中的第四趟排序后，待排序记录已按关键字有序排列，则起泡排序便在此趟排序后终止。为了实现这一点，我们可以在起泡排序算法(算法9.3)中引入一个布尔量swap，在每趟排序开始前，先将其置为0，若排序过程中发生了交换，则将其置为1。在一趟排序之后，如果swap仍为0，则表示本趟未曾交换过记录，此时可以终止算法。算法9.3起泡排序。下面分析起泡排序的性能。若记录已按关键字有序排列，则只需进行一趟扫描，而且比较次数和记录移动次数均为最小值：比较次数为n-1，记录移动次数为0；若记录逆序排列，即按关键字递减排列，则一共需进行n-1趟扫描，比较次数和记录移动次数均达到最大值，分别为由此可知，起泡排序的时间复杂度为O(n2)。为提高起泡排序算法的效率，必须减少算法9.3中的比较和交换次数。除了设置交换标志外，我们还可做如下两种改进：(1)在算法9.3中，一次扫描可以把最轻的气泡上升至顶，而最重的气泡仅能“下沉”一个位置。由此分析可知，对于关键字序列{2,3,7,8,9,1}，仅需一趟扫描就可以完成排序；但是对于关键字序列{9,1,2,3,7,8}，却需要从下向上扫描五趟才能完成排序。这两个序列都是仅有一个元素需要重排，但是产生了完全不同的结果。究其原因，正是扫描的方向导致了两种情况下的不对称性。如果改变扫描方向为从上向下，则序列{9,1,2,3,7,8}也仅需一趟扫描。基于上述分析，我们可在排序过程中交替改变扫描方向，形成双向起泡算法。(2)在每趟扫描中，记住最后一次交换发生的位置k，因为该位置之前的记录都已有序，即R[1,…,k-1]是有序区，R[k,…,n]是无序区，那么下一趟沿该方向扫描时可提前终止于位置k+1，而不必进行到预定的下界i+1，从而减少排序的趟数。9.3.2快速排序快速排序(QuickSort)是对起泡排序的一种改进，其基本思想是：通过一趟排序将记录序列分成两个子序列，然后分别对这两个子序列进行排序，以达到整个序列有序。假设待排序记录为R[s]～R[t]，任取其中一个记录R[p]作为比较的“基准”(pivot)，一般取p=s(s为子序列的下界)。用此基准将当前序列划分为左右两个子序列：R[s]～R[i-1]和R[i+1]～R[t]，使左边子序列的关键字均小于或等于基准的关键字，右边子序列的关键字均大于或等于基准的关键字，即R[s]～R[i-1].key≤R[i].key≤R[i+1]～R[t].key(s≤i≤t)此时基准所处的位置为R[i]，也即该记录的最终排序位置。这是一趟快速排序的过程。可以看出，快速排序中的比较都是与基准进行的，发生交换时记录移动的距离较大；而在起泡排序中，比较和交换是在相邻两记录之间进行的，每次交换记录只能前移或后移一个位置，因此快速排序的效率得到提高。快速排序是一种缩小规模算法。当R[s]～R[i-1]和R[i+1]～R[t]均非空时，还应分别对它们进行上述的划分过程，直至所有记录均已排好序为止。对序列R[s]～R[t]进行划分的具体做法为：基准设置为序列中的第一个记录R[s]，并将它保存在pivot中；设置两个指针low和high，它们的初值分别取为low=s和high=t；先令high自t起从右向左扫描，当找到第一个关键字小于pivot.key的记录R[high]时，将记录R[high]移至R[low](即空出数组单元R[high])；然后令low=low+1并从左向右扫描，当找到第一个关键字大于pivot.key的记录R[low]时，将记录R[low]移至R[high](即空出数组单元R[low])；接着令high=high-1并从右向左扫描，如此交替改变扫描方向，从两端各自往中间靠拢，直至low=high，此时low便是基准的最终位置；最后将pivot放在此位置上就完成了一次划分。算法9.4和算法9.5分别给出了一次划分算法及快速排序递归算法。算法9.4一次划分算法。算法9.5快速排序递归算法。算法9.5中数组R的下界s和上界t确定待排序记录的范围。对整个序列进行排序时，则调用QuickSort(R,1,n)。图9.4给出了一次划分的过程及整个快速排序的过程。下面分析快速排序算法的性能。可以证明，对n个记录进行快速排序的平均时间复杂度为O(n lb n)。在时间复杂度量级相同的算法中，快速排序也被公认是最好的。假设对长度为n的序列进行快速排序所需的比较次数为C(n)，则C(n) = Cp(n) + C(m) + C(n-m-1)其中，Cp(n)是进行一次划分所需的比较次数；m为一个子序列的长度。显然，Cp(n)与序列长度n有关。设Cp(n) = cn，c为常数，C(m)和C(n-m-1)分别是左、右两个子序列进行排序所需的比较次数，根据算法9.5，递归地对左、右两个子序列进行排序即可得到总的比较次数。在最好情况下，快速排序每次划分后基准左、右两个子序列的长度大致相等，也即所取的基准正好是待划分序列的“中值”。这样总的划分结果类似于一棵左右子树结点个数基本相等的二叉树。假设序列长度n = 2k，那么总的比较次数为当待排序记录已按关键字有序或基本有序时，快速排序的效率反而降低。在最坏情况下，每次划分后基准左、右两个子序列中有一个长度为0，这样总的划分结果则类似于一棵单支的二叉树。以有序序列为例，在第一趟快速排序中，经过n-1次比较之后，第一个记录仍定位在它原来的位置上，并得到一个包括n-1个记录的子序列；第二次递归调用中需经过n-2次比较，第二个记录仍定位在它原来的位置上，得到的子序列长度为n-2；依次类推，最后，得到总比较次数为这种情况下，快速排序的时间复杂度为O(n2)，蜕化为起泡排序。要改善此时的性能，通常采用“三者取中”的方法。也就是在进行一趟快速排序之前，对R[s].key、R[t].key和R[(s+t)/2].key进行比较，将三者中的“中值”记录与R[s]交换。实验证明，这种方法可以大大改善快速排序在最坏情况下的性能。综上所述，快速排序的最坏时间复杂度应为O(n2)，最好时间复杂度为O(n lb n)。9.4选择排序9.4.1直接选择排序直接选择排序(StraightSelectSort)又称为简单选择排序，其基本思想是：每一趟从待排序记录中选出关键字最小的记录，依次放在已排序记录的最后，直至全部记录有序。直接选择排序是其中最为简单的一种方法。直接选择排序的具体做法是：第一趟排序将待排序记录R[1]～R[n]作为无序区，从中选出关键字最小的记录并与无序区中第1个记录R[1]交换，此时得到的有序区为R[1]，无序区缩小为R[2]～R[n]；第二趟排序则从无序区R[2]～R[n]中选出关键字最小的记录，将它与R[2]交换；第i趟排序时，从当前的无序区R[i]～R[n]中选出关键字最小的记录R[k]，并与无序区中第1个记录R[i]交换，得到新的有序区R[1]～R[i]。注意：每趟排序从无序区中选择的记录，其关键字是有序区中的最大值。根据上述过程类推，进行n-1趟排序后，无序区中只剩一个记录，此时整个序列就是递增有序的。排序过程如图9.5所示，相应过程的C语言描述详见算法9.6。算法9.6直接选择排序。分析算法9.6可知，直接选择排序需n-1趟排序，每一趟的比较次数与关键字的排列状态无关。第一趟找出最小关键字需要进行n-1次比较，第二趟找出次小关键字需要进行n-2次比较，由此类推，总的比较次数为每趟比较后要判断是否要进行两个记录的交换，交换则要进行三次记录的移动。因此，直接选择排序在最好情况下，记录移动次数的最小值为0，最坏情况下最大值为3(n-1)。综上所述，直接选择排序的时间复杂度为O(n2)。这种排序方法是不稳定的。9.4.2堆排序堆排序(HeapSort)是直接选择排序的一种改进。在前面介绍的直接选择排序中，为了从R[1,…,n]中选出关键字最小的记录，必须进行n-1次比较；然后在剩余的无序区R[2,…,n]中找到关键字最小的记录，又需要做n-2次比较。事实上，后面这n-2次比较中有许多比较可能前面的n-1次比较中已经做过，但由于前一趟n-1次比较未保留这些比较结果，因此后一趟排序又重复了这些比较操作。堆排序正是以如何减少记录的比较次数为出发点的一种改进算法。堆排序是在排序过程中，将按照向量存储的记录看成一棵完全二叉树，利用完全二叉树中双亲结点和孩子结点之间的序号关系来选择关键字最小(最大)的记录。因此，堆排序的记录仍然按照数组顺序存储，而非采用树的存储结构，仅仅是借助完全二叉树的顺序结构特征进行分析而已，也就是该记录数组从逻辑上可看作是一个堆结构。1.堆的定义堆是具有以下性质的完全二叉树：所有非终端结点(非叶子结点)的关键字都大于或等于其左、右孩子结点的关键字，即满足条件R[i].key≥R[2i].key并且R[i].key≥R[2i+1].key，这样的完全二叉树称为大根堆；所有非终端结点(非叶子结点)的关键字都小于或等于其左、右孩子结点的关键字，即满足条件R[i].key≤R[2i].key并且R[i].key≤R[2i+1].key，这样的完全二叉树称为小根堆。从堆的定义我们可以看出，一个完全二叉树如果是堆，则每棵子树都是堆，且根结点(称为堆顶)一定是当前所有结点中的最大者(大根堆)或最小者(小根堆)。例如序列{49,33,42,20,26,30,35,10,15}是一个大根堆，序列{10,20,15,33,26,30,35,49,42}是一个小根堆。这两个堆的完全二叉树表示及一维数组存储表示如图9.6所示。以下讨论中以大根堆为例。2.堆排序1)堆排序的基本思想堆排序的基本思想是：首先将n个待排序记录序列构建成一个大根堆，此时，整个序列的最大值就是堆顶的根结点(一个记录对应一个结点)；接着将其与末尾结点(记录)交换，此时末尾结点就为最大值；然后再将剩余n-1个结点重新调整成一个堆，这样会得到n个记录序列中次大的记录。如此反复执行n-1趟堆排序，便能得到一个有序(正序)序列。2)堆排序需要解决的关键问题在堆排序中，需要解决的关键问题是：(1)如何按堆的定义构建一个堆，即建立初始堆。(2)如何处理堆顶结点。(3)如何调整剩余结点，成为一个新的堆，即重建堆。下面通过示例详细介绍堆排序的实现过程。如待排序记录序列为{47,33,25,82,72,11}，一般情况下，升序采用大根堆，降序采用小根堆。关键问题(1)：构建初始堆。用给定无序序列{47,33,25,82,72,11}构建成一个大根堆，下面介绍初始堆的构建过程。显然，无序序列{47,33,25,82,72,11}对应的图9.7(a)是一棵完全二叉树，但不是一个堆。由二叉树的性质可知，所有序号大于

的树叶结点已经是堆(无子结点)。因此，初始建堆从序号为

的最后一个非叶子结点开始，通过调整使所有序号小于等于

的结点为根结点的子树都满足堆的定义。在对根结点为i (如图9.7(b)中结点33)的子树建堆过程中，可能要对结点的位置进行调整(交换33和82)，以满足堆的定义。但这种调整可能会导致原先是堆的下一层子树不再满足堆的定义的情况(如图9.7(c)所示)，这就需要再对下一层进行调整，如此一层层进行下去，直到叶子结点。这种建堆方法就像过筛子一样，把最大结点向上逐层筛选到根结点位置，把小的结点筛选到下层，该过程称为筛选(sift)。建初始堆的过程如图9.7所示。关键问题(2)：分区。在初始堆建好后，将待排序结点序列分成无序区和有序区两部分，无序区是一个堆，有序区为空。此时将堆顶与堆中最后一个结点交换，则堆中减少一个结点，有序区增加一个结点，完成第一趟排序。以图9.7(e)为例，则是交换结点82和结点11，于是有序区不再为空，而是有一个记录82，如图9.8所示。一般情况下，第i趟堆排序对应的堆中有

个结点，即堆中最后一个记录是

。将R[1]和

交换完成第i趟排序。关键问题(3)：重新建堆。重新建堆也就是如何将堆中剩余的

个结点调整为堆。由关键问题(2)的处理结果(图9.8)可知，这个

结点(即序列{11,72,25,33,47})序列相比之前的堆，只有堆顶结点(已交换成11)发生了改变，其余结点未发生改变，即根结点11的左、右子树都是堆，以11为根结点的子树不是堆。因此，此时要解决的问题是如何调整根结点11，使得

个结点构成的整棵二叉树成为一个堆。下面在图9.8(b)的基础上介绍重新建堆过程。首先将结点11和其左、右孩子比较，根据堆的定义，应将11和72交换，如图9.9(a)所示。经过这一次交换，破坏了原来左子树的堆结构，需要对左子树再进行调整，如图9.9(b)所示。调整后的堆如图9.9(c)所示。其余各趟排序后的重新建堆操作过程都类似。3)堆排序的操作过程综上可知，堆排序的操作过程(大根堆)如下(小根堆类似)：(1)将初始待排序关键字序列(R1，R2，…，Rn)构建成大根堆，此堆为初始的无序区；构建过程中每个非叶子结点都经过一次调整，调整顺序为从底层至顶层(调整过程中含有递归)，这样调整下来这棵二叉树整体上就是一个大根堆了，见图9.7。(2)将堆顶元素R[1]与最后一个元素R[n]交换，得到新的无序区(R1，R2，…，Rn-1)和新的有序区(Rn)，且满足

，见图9.8。(3)将新的无序区调整为新的堆。由于交换后新的堆顶R[1]可能不满足堆的性质，因此需要将当前的无序区(R1，R2，…，Rn-1)调整为新堆，见图9.9；然后再次将R[1]与无序区最后一个元素R[n-1]交换，得到新的无序区(R1，R2，…，Rn-2)和新的有序区(Rn-1，Rn)。不断重复此过程，直到有序区的元素个数为n-1，则整个排序过程完成，见图9.10。因此对于堆排序，最重要的两个操作就是构建初始堆和调整堆。事实上，构造初始堆的过程也是调整堆的过程，只不过构造初始堆是对所有的非叶子结点都进行调整，而其余各趟重新调整建堆则是从整棵完全二叉树的树根开始调整。自堆顶至叶子的调整过程称为“筛选”。3.堆排序算法下面先给出基于大根堆筛选调整堆的伪代码，然后给出筛选调整堆的算法。筛选调整堆用伪代码描述为：假设当前要筛选结点的编号为s，堆中最后一个结点的编号为t，并且结点s的左、右子树均为堆，即R[s+1]～R[t]满足堆的条件，堆调整算法如下：算法9.7筛选调整堆的算法。下面为堆排序算法。算法9.8堆排序算法。堆排序是一种选择排序，它的运行时间主要消耗在初始建堆和重建堆时进行的反复筛选调整上。初始建堆需要O(n lb n)时间，第i次取堆顶结点重建堆需要O(n lb i)时间，并且n-1趟排序需要取n-1次堆顶结点，因此总的实际复杂度为O(n lb n)。堆排序的最坏、最好、平均时间复杂度均为O(n lb n)，它对原始记录序列的排列状态不敏感。相对于快速排序，这是堆排序最大的优点。在堆排序算法中，只需要一个用于交换的暂存单元，所以算法的空间复杂度为O(1)。堆排序是一种不稳定的排序算法。9.5归并排序1．二路归并排序的实现过程二路归并排序的具体实现分为三步：1)一次归并一次归并算法是将相邻的两个有序子表归并为一个有序子表。假设R[low]～R[mid]和R[mid + 1]～R[high]表示同一数组中相邻的两个有序表，现在要将它们合并为一个有序表R1[low]～R1[high]，需要设置三个指示器i、j和k，其初值分别为这三个记录区的起始位置，具体实现如算法9.9所示。算法9.9一次归并算法。在算法9.9中，从两个有序表R[low]～R[mid]和R[mid+1]～R[high]的左端开始，依次比较R[i]和R[j]的关键字，并将关键字较小的记录复制到R1[k]中；然后指向被复制记录的指示器和指向复制位置的指示器k右移，重复这一过程，直至其中一个有序表中全部记录复制完毕；最后将另一个有序表的剩余记录直接复制到数组R1[low]～R1[high]中。2)一趟归并假设在待排序序列中，每个有序表的长度均为length(最后一个有序表的长度可能小于length)，那么在归并前R[1]～R[n]中共有n/length个有序的子表：R[1]～R[length]，R[length+1]～R[2length],…,R[(n/length-1)length+1]～R[n]。一趟归并算法多次调用一次归并算法将相邻的一对有序表进行归并，完成一趟排序，具体算法见算法9.10。算法9.10一趟归并算法。算法9.10中要考虑到三种情况，即有序表的个数为偶数且长度均为length、有序表的个数为偶数但是最后一个有序表长度小于length以及有序表的个数为奇数。3)归并排序归并排序算法如算法9.11所示，实际上就是对“一趟归并”的重复调用过程。有序表的初始长度为1，每趟归并后有序表长度增大一倍；若干趟归并后，当有序表的长度等于n时，排序结束。算法9.11归并排序算法。2．二路归并排序示例及算法性能分析图9.11所示为归并排序的示例。对于一组待排序的记录，其关键字分别为49,31,63,85,75,15,26,49。根据算法9.9，首先将这8个记录看作是长度为1的8个有序表，然后两两归并，直至有序表的长度不小于8。分析算法9.9、算法9.10以及图9.11可知，第i趟归并后，有序表长度为2i。因此，对于长度为n的无序表，必须执行

趟归并。每趟归并的时间复杂度是O(n)，二路归并排序算法的时间复杂度为O(n lb n)。算法中的辅助空间即数组R1的长度为n，因此空间复杂度是O(n)。归并排序是一种稳定的排序算法。与快速排序算法相比，这是它的最大特点。实际应用中并不提倡从长度为1的序列开始进行二路归并。可以先利用直接插入排序得到较长的有序表，然后再进行两两归并。二者的混合排序仍然是稳定的。9.6基数排序9.6.1多关键字排序的概念1．多关键字的排序过程多关键字排序的定义：给定一个含有n个记录的序列{R1,R2,…,Rn}，每个记录Ri含有d个关键字

。多关键字排序是指对d个关键字有序，即对于序列中任意两个记录Ri和Rj(

)都满足如下有序关系：2．多关键字的排序方法多关键字排序按照从最主位关键字到最次位关键字或从最次位关键字到最主位关键字的顺序逐次排序，有两种基本的方法：1)最次位优先法最次位优先法简称LSD法(LeastSignificantDigitFirst)，是指先从kd开始分组和收集，同一组记录具有相同的关键字kd，再按kd-1进行分组和收集，依次重复，直到按最主位关键字k1进行分组和收集后得到一个有序序列为止。2)最主位优先法最主位优先法简称MSD法(MostSignificantFirst)，是指先按最主位关键字k1进行分组和收集，同一组子序列中的记录具有相同的关键字k1；再对各组子序列按k2排序分割成若干更小的子序列，每个更小的子序列具有相同的k2；依此类推，直到按最次位关键字kd对各子组分组和收集后得到一个有序序列为止。9.6.2基数排序的过程及链式基数排序算法1．基数排序的基本思想基数排序是指将待排序记录的关键字看成由若干个子关键码(字)复合而成，每个子关键码作为一个“关键字”。比如关键字为3位整数，则可以把关键字拆分成3个关键字，每位看成一个关键字，然后对单关键字的排序就可以按上述介绍的多关键字排序方法进行。拆分后的每个关键字的取值范围相同，我们称这个取值范围为“基”，并记作r。基于LSD的基数排序的基本思想是：根据