《软件技术基础》课件第9章

9.1排序的基本概念9.2插入排序9.3交换排序9.4直接选择排序9.5归并排序9.6各种内部排序方法的比较和选择习题9第9章排序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)算法执行所需要的附加空间。另外要考虑的一个因素是算法本身的复杂程度。排序算法所需的附加空间量一般都不大，所以排序算法的时间复杂度是衡量算法好坏的最重要的标志。排序所需的时间主要是指算法执行中关键字的比较次数和记录的移动次数。因此，后面的章节将会详细讨论排序算法中的比较次数和移动次数。

待排序的记录可有下列三种存储结构：

(1)以一组连续的地址单元(如一维数组)作为存储结构，待排序记录的次序由其物理位置决定。在排序过程中，必须移动记录来进行物理位置上的重排，即通过比较和判定把记录移到合适的位置。

(2)以链表作为存储结构，记录之间的次序由指针决定。因此，在排序过程中仅需修改指针。

(3)待排序记录存储在一组连续的地址单元内，此时若要避免排序过程中记录的移动，可以为该序列建立一个辅助表(如索引表)，在排序过程中只需对这个辅助的表目进行物理重排，而不移动记录本身。

为方便起见，本章假设记录序列的存储结构为一维数组，关键字为整数。待排序记录的数据类型说明如下：

typedefstruct //定义记录为结构类型

{intkey; //关键字域

datatypeother; //其他数据域

}rectype;

rectypeR[n+1];//n为记录总数，R[0]闲置或作为哨兵单元

9.2.1直接插入排序

直接插入排序(StraightInsertionSort)是一种最简单的排序方法。其基本思路是把关键字ki依次与有序区的关键字ki-1,ki-2,

…,k1进行比较，找到应该插入的位置，然后将ki插入。给定待排序的记录序列为R[1]～R[n]，则初始有序区为{R[1]}，直接插入排序可以从i=2开始，如算法9.1所示。9.2插入排序算法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对待排序的一组记录进行排序，记录的关键字分别为49,31,63,85,75,15,26,49

，直接插入排序过程如图9.1所示。

直接插入排序的算法9.1非常简洁，容易实现，下面来分析它的效率。

从时间上看，整个排序过程只有两种运算，即比较关键字和移动记录。算法中的外循环表示要进行n

1趟插入排序，内循环的次数则取决于待排序关键字与有序区中i个关键字的关系。

图9.1直接插入排序示例可以按两种情况来考虑。当一组记录为正序时(这里按递增有序)，每趟排序的关键字比较次数为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希尔排序示例由图9.2可见，希尔排序的每一趟就是直接插入排序。增量越大，则得到的子序列越短，此时直接插入排序效率很高；而当增量逐渐减小时，序列已逐渐有序，因此直接插入排序仍然很有效。当增量为1时，此时所有的记录已经基本有序，并放在同一组中进行直接插入排序。由此，希尔排序的速度较直接插入排序有很大的提高。

要注意的是，希尔排序中的子序列不是逐段选取的，而是根据增量值跳跃性的抽取。这样可以实现排序记录在较大范围内进行移动，从而提高了排序速度。但是由此导致了希尔排序是不稳定的。

希尔排序的具体算法描述如算法9.2所示。

算法9.2中没有设置“监视哨”，单元R[0]仅作为暂存单元，在内循环中增加了一个循环判定条件“j>0”，以防下标越界。若要设置监视哨，需要利用数组R的前t个单元作为监视哨，待排序记录则要从第t个单元开始存储。读者可以自行完成。

希尔排序的时间复杂度取决于增量序列的选取，但是如何选取增量序列才能产生最好的排序效果，这一问题至今没有得到解决。希尔本人最初提出取d1=

n/2

，di+1=

di/2

，dt=1，t=

lb n

，后来又有人提出其他选择增量序列的方法，如di+1=

(di

1)/3

，dt=1，t=

log3n

1

以及di+1=

(di

1)/2

，dt=1，t=

lb n

1

。大量实验表明，希尔排序所需的比较和移动次数约为n1.3。

9.3.1起泡排序

起泡排序(BubbleSort)是最为人们所熟知的交换排序方法。它的过程非常简单：对纵向排列的关键字序列，按照自下而上的扫描方向对两两相邻的关键字进行比较，若为逆序(即kj

1>kj)，则将两个记录交换位置；重复上述扫描排序过程，直至没有记录需要交换为止。

9.3交换排序第一趟扫描后，关键字最小的记录将上升到第一个记录的位置上；第二趟对后面的n

1个记录重复同样操作，把次小关键字的记录安排在第二个记录的位置上；重复上述过程，分析可知，在第n

1趟后，全部记录都按关键字由小到大的顺序排列完毕。在每一趟排序过程中，关键字最小的记录通过比较和交换，会像气泡一样上浮至顶，而关键字较大的记录则逐渐下沉，“起泡排序”的名称由此而来。起泡排序的过程如图9.3所示。

图9.3从下向上扫描的起泡排序示例(实际只扫描了5趟)对任一组记录进行起泡排序时，至多需要进行n

1趟排序。但是，如果在排序过程中的某一趟扫描后，例如图9.3中的第四趟排序后，待排序记录已按关键字有序，因此起泡排序便可在此趟排序后终止。为了实现这一点，可以在起泡排序算法(算法9.3)中引入一个布尔量swap，在每趟排序开始前，先将其置为FALSE，若排序过程中发生了交换，则将其置为TRUE。在一趟排序之后，如果swap仍为FALSE，则表示本趟未曾交换过记录，此时可以终止算法。

下面分析起泡排序的性能。若记录已按关键字有序排列，则只需进行一趟扫描，而且比较次数和记录移动次数均为最小值：比较次数为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，从而减少排序的趟数。例如，第一趟排序后的序列为1，2，3，9，8，7，最后一次交换的位置为k=4，那么下一趟扫描的下界可设为5，而不是3。改进的算法见本章习题第四大题的第14小题。

9.3.2快速排序

快速排序是对起泡排序的一种改进，其基本思想是：通过一趟排序将记录序列分成两个子序列，然后分别对这两个子序列进行排序以达到整个序列有序。

假设待排序记录为R[s]～R[t]，任取其中一个记录R[p]作为比较的“基准”(pivot)，一般取p=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.5中，数组R的下界s和上界t确定了待排序记录的范围。对整个序列进行排序时，则调用QuickSort(R,1,n)。

图9.4给出了一次划分的过程及整个快速排序的过程。

图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，那么总的比较次数为

C(n)≤Cp(n)+C(n/2)+C(n/2)=cn+2C(n/2)

≤cn+2[cn/2+2C(n/22)]=2cn+4C(n/22)

≤2cn+4[cn/4+2C(n/23)]=3cn+8C(n/23)

≤……

≤ckn+2kC(n/2k)=c(lb n)O(n)+nC(1)

=O(n lb n)

式中C(1)是一常数。

当待排序记录已按关键字有序或基本有序时，快速排序的效率反而降低。在最坏情况下，每次划分后基准左、右两个子序列中有一个长度为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)。注意到，快速排序的记录移动次数不大于比较的次数。可以证明：平均情况下快速排序的时间复杂度也是O(n lb n)。从时间上看，它是目前基于比较的内部排序方法中平均性能最好的，因而称为快速排序。

从空间上看，快速排序算法虽然只需要一个临时单元存放基准记录，但是其递归特性需要一个栈空间来实现。栈空间的大小取决于每次划分后序列的长度。最好情况下，栈的最大深度为

lb n

+1，所需栈空间为O(lb n)；最坏情况下，栈的最大深度为n，所需栈空间为O(n)。

快速排序是不稳定的。

选择排序(SelectSort)的基本思想是：每一趟从待排序记录中选出关键字最小的记录，依次放在已排序记录的最后，直至全部记录有序。直接选择排序是其中最为简单的一种方法。

9.4直接选择排序直接选择排序的具体做法是：第一趟排序将待排序记录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.5直接选择排序示例分析算法9.6可知，直接选择排序需n

1趟排序，每一趟的比较次数与关键字的排列状态无关。第一趟找出最小关键字需要进行n

1次比较，第二趟找出次小关键字需要进行n

2次比较，由此类推，总的比较次数为

每趟比较后要判断是否进行两个记录的交换，如要交换，则进行三次记录的移动。因此直接选择排序在最好情况下，记录移动次数的最小值为0，而在最坏情况下的最大值为3(n

1)。

综上所述，直接选择排序的时间复杂度为O(n2)。这种排序方法是不稳定的。

归并排序(MergeSort)的思路与前面介绍过的排序方法都不一样。“归并”的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序的基本思路是：假设初始表含有n个记录，则可看成是n个有序的子表，每个子表的长度为1，然后两两归并，得到

n/2

个长度为2或1的有序子表；再两两归并，如此重复，直至得到一个长度为n的有序子表为止。这种方法称为“二路归并排序”。

9.5归并排序

1．二路归并

假设R[low]～R[mid]和R[mid+1]～R[high]表示同一数组中相邻的两个有序表，现在要将它们合并为一个有序表R1[low]～R1[high]，需要设置三个指示器i、j和k，其初值分别为这三个记录区的起始位置。具体实现如算法9.7所示。

在算法9.7中，从两个有序表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[2

length]，…，R[(

n/length

1)

length+1]～R[n]。一趟归并所解决的问题是，调用二路归并算法将相邻的一对有序表进行归并。具体算法见算法9.8。

在算法9.8中要考虑三种情况：有序表的个数为偶数且长度均为length，有序表的个数为偶数但最后一个有序表的长度小于length，有序表的个数为奇数。

3．二路归并排序

二路归并排序如算法9.9所示，实际上就是对“一趟归并”的重复调用过程。有序表的初始长度为1，每趟归并后有序表长度增大一倍；若干趟归并后，当有序表的长度大于或等于n时，排序结束。

要注意的是，算法9.9中每次循环调用函数MergePass两次。若第一次调用后，条件length<n成立，则第二次调用MergePass仍实现排序功能，否则排序已完成，此时第二次调用MergePass的作用仅仅是把排序结果从R1复制到R中。

图9.6所示为归并排序的示例。对于一组待排序的记录，其关键字分别为49,31,63,85,75,15,26,49

。根据算法9.9，首先将这8个记录看做是长度为1的8个有序表，然后两两归并，直至有序表的长度不小于8。图9.6二路归关排序示例分析算法9.9以及图9.6可知，第i趟归并后，有序表长度为2i。因此，对于长度为n的无序表，必须执行

lb n

趟归并。由于每趟归并的时间复杂度是O(n)，二路归并排序算法的时间复杂度为O(n lb n)，算法中辅助空间即数组R1的最大长度为n，因此空间复杂度是O(n)。

与快速排序算法相比，二路归并排序的最大特点是它是稳定的。

实际应用中并不提倡从长度为1的序列开始进行二路归并。可以先利用直接插入排序得到较长的有序表，然后再进行两两归并。二者的混合排序仍然是稳定的。

内部排序方法还有堆排序、分配排序、基数排序等多种，本章不做一一介绍。各种排序方法中没有哪一种是绝对最优的，不同排序方法各有其优缺点，因此，在不同的场合根据需要选择适当的排序方法是十分重要的。综合比较本章所讨论的各种排序方法，大致有如表9.1所示的结果，其中简单排序包括除希尔排序之外的所有插入排序、起泡排序和简单选择排序。

9.6各种内部排序方法的比较和选择具体选择排序方法时，应考虑以下因素：

(1)平均时间：平均时间主要取决于算法的时间复杂度以及关键字的分布情况。一般应采用时间复杂度为O(n lb n)的排序方法，例如快速排序、归并排序。当待排序的关键字随机分布时，快速排序所需运行时间最短，但是在最坏情况下性能较差。归并排序没有所谓的最坏情况，当n较大时可作为另一种较好的选择。

(2)记录数目n：若n比较小(如n≤50)，则可采用简单的排序方法，而直接插入排序最为简单。当序列中的记录基本有序时，直接插入排序或起泡排序是较好的选择。当n较大时，可根据平均时间来考虑。

(3)记录大小：排序算法中的主要操作是关键字的比较和记录的移动。当记录本身数据量较大时，应采用记录移动次数较少的排序方法，例如直接插入排序所需的记录移动次数要多于直接选择排序。

(4)稳定性：这一点取决于不同的应用场合。当稳定性比较重要时，较快的算法可以选择归并排序或基数排序，简单排序中可以选择直接插入排序、起泡排序等。必须注意的是，稳定的排序方法与其具体的描述形式有关，改变描述形式后，原本稳定的排序方法也会变得不稳定。

本章所讨论的内部排序算法都是在一维数组上实现的。当记录本身的信息量较大时，采用链表结构可以节约因大量移动记录所耗费的时间。当记录很大时，可以采用静态链表作为存储结构，以指针的修改替代记录的移动。另外，对于任何链表结构，我们还可以提取结点的地址信息存储为地址向量，然后按照一位数组的方式对该地址向量进行排序。

一、名词解释

排序，稳定的排序，不稳定的排序，内部排序，外部排序

二、填空题

1．按照排序过程涉及的存储设备的不同，排序可分为

排序和

排序。

2．在排序算法中，分析算法的时间复杂性时，通常以

和

为标准操作。评价排序的另一个主要标准是执行算法所需要的

。

3．直接插入排序是稳定的，它的时间复杂性为

，空间复杂度为

。

习题9

4．对于n个记录的集合进行起泡排序，其最坏情况下所需的时间复杂度为

。

5．对于n个记录的集合进行归并排序，所需的附加空间消耗是

。

6．以下为起泡排序的算法。请分析算法，并在

上填充适当的语句。

7．对快速排序来讲，其最好情况下的时间复杂度是

，其最坏情况下的时间复杂度是

。

8．归并排序要求待排序列由若干个

的子序列组成。

三、选择题

1．以下不稳定的排序方法是()。

A.直接插入排序

B.起泡排序

D.直接选择排序

D.二路归并排序

2．以下时间复杂性不是O(n2)的排序方法是()。

A.直接插入排序

B.二路归并排序

C.起泡排序

D.直接选择排序

3．排序的目的是为了以后对已排序的数据元数进行()操作。

A.打印输出 B.分类