1、2018/9/30,1,第8章 排序,排序的概念及种类 插入法排序的各种具体实现方法及算法分析 选择法排序的各种具体方法的实现及时间性能分析 交换法排序的具体实现及性能分析 归并排序和基数排序的各自实现算法,2018/9/30,2,本章导读,排序是日常工作和软件设计中常用的运算之一。为了提高查询速度需要将无序序列按照一定的顺序组织成有序序列。由于需要排序的数据表的基本特性可能存在差异，使得排序方法也不同。如何合理地组织数据的逻辑顺序，按照何种方式排出的序列最有效？这是本章要讨论的主题。本章主要介绍排序的概念及几种最常见的排序方法，讨论其性能和特点，并在此基础上进一步讨论各种方法的适用场合，以便
2、在实际应用中能根据具体的问题选择合适的排序方法。通过本章学习，读者应该掌握以下几项内容： 排序的概念及种类 插入法排序的各种具体实现方法及算法分析 选择法排序的各种具体方法的实现及时间性能分析 交换法排序的具体实现及性能分析 归并排序和基数排序的各自实现算法,2018/9/30,3,8.1 排序的基本概念,8.1.1 排序及其分类,1排序概念,排序（sorting）又称分类，是数据处理领域中一种很常用的运算。排序就是把一组记录或数据元素的无序序列按照某个关键字值（关键字）递增或递减的次序重新排列的过程。排序的主要目的就是实现快速查找。日常生活中通过排序以后进行检索的例子屡见不鲜。如电话簿、病历
3、、档案室中的档案、图书馆和各种词典的目录表等，几乎都需要对有序数据进行操作。,2018/9/30,4,假设含有n个记录的序列为：R1，R2 ，Rn (8-1)其相应的关键字序列为： K1，K2 ，Kn需确定1，2， ，n的一种排序p1，p2， ，pn，使其相应的关键字满足如下关系：Kp1Kp2Kpn (8-2)即使得式（8-1）的序列成为一个按关键字有序的序列R p1，R p2 ，Rpn (8-3) 这个将原有表中任意顺序的记录变成一个按关键字有序排列的过程称为排序。,2018/9/30,5,2排序分类,增排序和减排序：如果排序的结果是按关键字从小到大的次序排列的，就是增排序，否则就是减排序。
4、 稳定排序和不稳定排序：假设Ki=Kj（1in，1jn，ij），且在排序前的序列中Ri领先于Rj（即ij）。若在排序后的排序中Ri仍领先于Rj，即那些具有相同关键字的记录，经过排序后它们的相对次序仍然保持不变，则称这种排序方法是稳定的；反之，若Rj领先于Ri，则称所用的方法是不稳定的。,2018/9/30,6,(3) 内部排序与外部排序：在排序中，若数据表中的所有记录的排列过程都是在内存中进行的，称为内部排序。由于待排序的记录数量太多，在排序过程中不能同时把全部记录放在内存，需要不断地通过在内存和外存之间交换数据元素来完成整个排序的过程，称为外部排序。在外部排序情况下，只有部分记录进入内存，在
5、内存中进行内部排序，待排序完成后再交换到外部存储器中加以保存。然后再将其它待排序的记录调入内存继续排序。这一过程需要反复进行，直到全部记录排出次序为止。显然，内部排序是外部排序的基础，本章先介绍内部排序的各种方法，最后再讨论外部排序。,2018/9/30,7,8.1.2 排序算法的效率分析,与许多算法一样，对各种排序算法性能的评价主要从两个方面来考虑，一是时间性能；二是空间性能。,1 时间复杂度分析,排序算法的时间复杂度可用排序过程中记录之间关键字的比较次数与记录的移动次数来衡量。在本章各节中讨论算法的时间复杂度时，一般都按平均时间复杂度进行估算；对于那些受数据表中记录的初始排列及记录数目影响
6、较大的算法，按最好情况和最坏情况分别进行估算。,2018/9/30,8,2空间复杂度分析,排序算法的空间复杂度是指算法在执行时所需的附加存储空间，也就是用来临时存储数据的内存使用情况。 在以后的排序算法中，若无特别说明，均假定待排序的记录序列采用顺序表结构来存储，即数组存储方式，并假定是按关键字递增方式排序。为简单起见，假设关键字类型为整型。待排序的顺序表类型的类型定义如下： typedef int KeyType /定义关键字类型 typedef struct dataType /记录类型 keytype key; /关键字项 elemtype otherelement; /其他数据项 Re
7、cType;,2018/9/30,9,8.2 插入排序,插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。也就是说，将待序列表分成左右两部分，左边为有序表（有序序列），右边为无序表（无序序列）。整个排序过程就是将右边无序表中的记录逐个插入到左边的有序表中，构成新的有序序列。根据不同的插入方法，插入排序算法主要包括：直接插入排序、折半插入排序、表插入排序和希尔排序等。本章重点介绍直接插入排序、折半插入排序和希尔排序。,2018/9/30,10,8.2.1 直接插入排序,直接插入排序(Insertion Sort)是所有排
8、序方法中最简单的一种排序方法。其基本原理是顺次地从无序表中取出记录Ri(1in)，与有序表中记录的关键字逐个进行比较，找出其应该插入的位置，再将此位置及其之后的所有记录依次向后顺移一个位置，将记录Ri插入其中。 假设待排序的n个记录为R1，R2 ，Rn，初始有序表为R1，初始无序表为R2 Rn。当插入第i个记录Ri(2in)时，有序表为R1Ri-1，无序表为Ri Rn。将关键字K i依次与Ki-1，Ki-2 ，K1进行比较，找出其应该插入的位置，将该位置及其以后的记录向后顺移，插入记录Ri，完成序列中第i个记录的插入排序。当完成序列中第n个记录Rn的插入后，整个序列排序完毕。,2018/9/3
9、0,11,向有序表中插入记录，主要完成如下操作：(1) 搜索插入位置。(2) 移动插入点及其以后的记录空出插入位置。(3) 插入记录。,假设将n个待排序的记录顺序存放在长度为n+1的数组R1Rn 中。R0作为辅助空间，用来暂时存储需要插入的记录，起监视哨的作用。直接插入排序算法如下:,2018/9/30,12,void Insert_Sort(int R,int n) int i,j; for(i=2;i=n; i+) /表示待插入元素的下标 R0=Ri; /设置监视哨保存待插入元素，腾出Ri空间 j=i-1; /j指示当前空位置的前一个元素 while(R0.keyRj.key)/搜索插入位
10、置并后移腾出空 Rj+1=Rj; j-; Rj+1=R0; /插入元素 ,2018/9/30,13,显然，开始时有序表中只有1个记录R1，然后需要将R2Rn的记录依次插入到有序表中，总共要进行n-1次插入操作。首先从无序表中取出待插入的第i个记录Ri，暂存在R0中；然后将R0.key依次与Ri-1.key，Ri-2.key，进行比较，如果R0.keyRi-j.key（1ji-1），则将Ri-j后移一个单元；如果R0.keyRi-j.key，则找到R0插入的位置i-j+1，此位置已经空出，将R0 (即Ri)记录直接插入即可。然后采用同样的方法完成下一个记录Ri+1的插入排序。如此不断进行，直到完
11、成记录Rn的插入排序，整个序列变成按关键字非递减的有序序列为止。在搜索插入位置的过程中，R0.key与Ri-j.key进行比较时，如果j=i，则循环条件 R0.keyRi-j.key不成立，从而退出while 循环。由此可见R0起到了监视哨的作用，避免了数组下标的出界。,2018/9/30,14,【例8-1】假设有7个待排序的记录，它们的关键字分别为23，4，15，8，19，24，15，用直接插入法进行排序。,【解】直接插入排序过程如图8-1所示。方括号 中为已排好序的记录的关键字，有两个记录的关键字都为15，为表示区别，将后一个15加下划线。,图8-1 直接插入排序,2018/9/30,15
12、,空间性能：该算法仅需要一个记录的辅助存储空间，空间复杂度为O(1)。时间性能：整个算法执行for循环n-1次，每次循环中的基本操作是比较和移动，其总次数取决于数据表的初始特性，可能有以下几种情况：（1）当初始记录序列的关键字已是递增排列时，这是最好的情况。算法中while语句的循环体执行次数为0，因此，在一趟排序中关键字的比较次数为1，即R0的关键字与Rj的关键字比较。而移动次数为2，即Ri移动到R0中，R0移动到Rj+1中。所以，整个排序过程中的比较次数和移动次数分别为(n-1)和2(n-1)， 因而其时间复杂度为O(n)。,稳定性：由于该算法在搜索插入位置时遇到关键字值相等的记录时就停止
13、操作，不会把关键字值相等的两个数据交换位置，所以该算法是稳定的。,2018/9/30,16,（2）当初始数据序列的关键字序列是递减排列时，这是最坏的情况。在第i次排序时， while语句内的循环体执行次数为i。因此，关键字的比较次数为i，而移动次数为i+1。所以，整个排序过程中的比较次数和移动次数分别为：,（3）一般情况下，可认为出现各种排列的概率相同，因此取上述两种情况的平均值，作为直接插入排序关键字的比较次数和记录移动次数，约为n2/4。所以其时间复杂度为O(n2)。根据上述分析得知：当原始序列越接近有序时，该算法的执行效率就越高。,2018/9/30,17,8.2.2 折半插入排序,直接
14、插入排序的基本操作是在有序表中进行查找和插入，而在有序表中查找插入位置，可以通过折半查找的方法实现，由此进行的插入排序称之为折半插入排序。 所谓折半查找，就是在插入Ri时（此时R1，R2，Ri-1已排序），取Ri/2的关键字Ki/2 与Ki进行比较（i/2 表示取不大于i/2的最大整数），如果KiKi/2，Ri的插入位置只能在R1和Ri/2 之间，则在R1和Ri/2-1之间继续进行折半查找，否则在Ri/2+1和Ri-1 之间进行折半查找。如此反复直到最后确定插入位置为止。折半查找的过程是以处于有序表中间位置记录的关键字和Ki比较，经过一次比较，便可排除一半记录，把可插入的区间缩小一半，故称为折
15、半。,2018/9/30,18,设置始指针low，指向有序表的第一个记录，尾指针high，指向有序表的最后一个记录，中间指针mid指向有序表中间位置的记录。每次将待插入记录的关键字与mid位置记录的关键字进行比较，从而确定待插入记录的插入位置。折半插入排序算法如下：,typedef int keytype;void Insert_halfSort(RecType R,int n)/*对顺序表R作折半插入排序*/ int i,j,low,high,mid;for(i=2; i=high+1; -j) /high+1为插入位置 Rj+1=Rj; /后移元素，空出插入位置 Rhigh+1=R0; /
16、将元素插入 ,2018/9/30,20,【例8-2】待排序记录的关键字为：28，13，72，85，39，41，6，20，在前7个记录都已排好序的基础上，采用折半插入第8个记录的比较过程如图8-2所示。,图8-2 折半插入排序,2018/9/30,21,折半插入排序的比较次数与待排序记录的初始排列次序无关，仅依赖于记录的个数。插入第i个元素时，如果i=2j（1jlog2n），则无论关键字值的大小，都恰好经过j= log2i次比较才能确定其应插入的位置；如果2ji2j+1，则比较次数为j+1。因此将n个记录（设n=2k）排序的总比较次数为：,2018/9/30,22,折半插入排序仅减少了关键字间的
17、比较次数，但记录的移动次数不变。因此折半插入排序的时间复杂度仍为O(n2)。折半插入排序的空间复杂度与直接插入排序相同。折半插入排序也是一个稳定的排序方法。,2018/9/30,23,8.2.3 希尔排序,希尔排序（shells sort）又称缩小增量排序(Diminishing Increment Sort)。它是希尔（D.L.Shell）于1959年提出的插入排序的改进算法。如前所述，直接插入排序算法的时间性能取决于数据的初始特性，一般情况下，它的时间复杂度为O(n2)。但是当待排序列为正序或基本有序时，时间复杂度则为O(n)。因此，若能在一次排序前将排序序列调整为基本有序，则排序的效率就
18、会大大提高。正是基于这样的考虑，希尔提出了改进的插入排序方法。 希尔排序的基本思想是：先将整个待排记录序列分割成若干小组（子序列），分别在组内进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。希尔排序的具体步骤如下：,2018/9/30,24,（1）首先取一个整数d1n，称之为增量，将待排序的记录分成d1个组，凡是距离为d1倍数的记录都放在同一个组，在各组内进行直接插入排序，这样的一次分组和排序过程称为一趟希尔排序。（2）再设置另一个新的增量d2d1，采用与上述相同的方法继续进行分组和排序过程。（3）继续取di+10) /通过增量控制排序的执行过程 for(
19、i=d; i=0) if(Rj.keyRj+d.key) temp=Rj; /Rj与Rj+d交换 Rj=Rj+d;Rj+d=temp;j=j-d; /j前移 else j=-1; d=d2; /递减增量d ,2018/9/30,28,从希尔排序过程可以看到： （1）算法中约定初始增量d1为已知； （2）算法中采用简单的取增量值的方法，从第二次起取增量值为其前次增量值的一半。在实际应用中，可能有多种取增量的方法，并且不同的取值方法对算法的时间性能有一定的影响，因而一种好的取增量的方法是改进希尔排序算法时间性能的关键。 （3）希尔排序开始时增量较大，分组较多，每组的记录数较少，故各组内直接插入过程
20、较快。随着每一趟中增量di逐渐缩小，分组数逐渐减少，虽各组的记录数目逐渐增多，但由于已经按di-1作为增量排过序，使序列表较接近有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。希尔排序的时间复杂度约为O(n1.3)，它实际所需的时间取决于各次排序时增量的取值。大量研究证明，若增量序列取值较合理，希尔排序时关键字比较次数和记录移动次数约为O(nlog2n)2。由于其时间复杂度分析较复杂，在此不做讨论。 希尔排序会使关键字相同的记录交换相对位置，所以希尔排序是不稳定的。,2018/9/30,29,8.3交换排序,利用交换记录的位置进行排序的方法称为交换排序。
21、其基本思想是：两两比较待排序记录的关键字，如果逆序就进行交换，直到所有记录都排好序为止。常用的交换排序方法主要有冒泡排序和快速排序。快速排序是一种分区交换排序法，是对冒泡排序方法的改进。,2018/9/30,30,冒泡排序（Bubble sort）的算法思想是：设待排序有n个记录，首先将第一个记录的关键字R1.key和第二个记录的关键字R2.key进行比较，若R1.keyR2.key，就交换记录R1和R2在序列中的位置；然后继续对R2.key和R3.key进行比较，并作相同的处理；重复此过程，直到关键字Rn-1.key和Rn.key比较完成。其结果是n个记录中关键字最大的记录被交换到序列的最后
22、一个记录的位置上，即具有最大关键字的记录被“沉”到了最后，这个过程被称为一趟冒泡排序。然后进行第二趟冒泡排序，对序列表中前n-1个记录进行同样的操作，使序列表中关键字次大的记录被交换到序列的n-1位置上；第i趟冒泡排序是从R1到Rn-i+1依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关,8.3.1 冒泡排序,2018/9/30,31,键字最大的记录被交换到n-i+1位置上。每一趟排序都有一个相对大的数据被交换到后面，就像一块块“大”石头不断往下沉，最大的总是最早沉下；而具有较小关键字的记录则不断向上（前）移动位置，就像水中的气泡逐渐向上飘浮一样，冒到最
23、上面的是关键字值最小的记录。所以把这种排序方法称为冒泡排序。对有n个记录的序列最多做n-1趟冒泡就会把所有记录依关键字大小排好序。如果在某一趟排序中都没有发生相邻记录的交换，表示在该趟之前已达到排序的目的，整个排序过程可以结束。在操作实现时，常用一个标志位flag标示在第i趟是否发生了交换，若在第i趟发生过交换，则置flag=false（或0）；若第i趟没有发生交换，则置flag=true（或1），表示在第i-1趟已经达到排序目的，可结束整个排序过程。,2018/9/30,32,算法描述如下：#define False 0#define True 1typedef int keytype;vo
24、id Bubble_Sort(RecType R,int n) /用冒泡排序对R1Rn记录排序 int i,j,flag=0;for(i=1; in; i+) flag=1 ; /每趟比较前设置flag=1，假定该序列已有序 for(j=1;j=n-i;j+) if(Rj+1.key26，进行第一次调整，将Rj.key (26) 放到Ri (i=1)处，Rj (j=7)位置空出；令i=i+1，然后进行从前往后的比较；当i=3时，tempRi.key (67)，进行第二次调整，将Ri.key (67) 放到Rj (j=7) 处，于是，Ri (i=3)位置空出；经过i和j交替地从两端向中间扫描以及
25、记录位置的调整，当执行到i=j=4 时，一趟排序成功，将temp保存的记录放入该位置，这也是该记录的最终排序位置。,2018/9/30,44,（2）各趟排序之后的结果,图8-6 快速排序过程,2018/9/30,45,快速排序算法的执行时间取决于基准记录的选择。一趟快速排序算法的时间复杂度为O(n)。下面分几种情况讨论整个快速排序算法需要排序的趟数： （1）在理想情况下，每次排序时所选取的记录关键字值都是当前待排序列中的“中值”记录，那么该记录的排序终止位置应在该序列的中间，这样就把原来的子序列分解成了两个长度大致相等的更小的子序列，在这种情况下，排序的速度最快。设完成n个记录待排序列所需的比
26、较次数为C(n),则有：C(n)n+2C(n/2)2n+4C(n/4)kn+nC(1)(k是序列的分解次数) 若n为2的幂次值且每次分解都是等长的，则分解过程可用一棵满二叉树描述，分解次数等于树的深度k=log2n，因此有：C(n)nlog2n+nC(1)=O(nlog2n)整个算法的时间复杂度为O(nlog2n)。,2018/9/30,46,(2)在极端情况下，即每次选取的“基准”都是当前分组序列中关键字最小(或最大)的值，划分的结果是基准的前边(或右边)为空，即把原来的分组序列分解成一个空序列和一个长度为原来序列长度减1的子序列。总的比较次数达到最大值：,如果初始记录序列已为升序或降序排列
27、，并且选取的基准记录又是该序列中的最大或最小值，这时的快速排序就变成了“慢速排序”。整个算法的时间复杂度为O(n2)。为了避免这种情况的发生，可修改上面的排序算法，在每趟排序之前比较当前序列的第一、最后和中间记录的关键字，取关键字居中的一个记录作为基准值调换到第一个记录的位置。,2018/9/30,47,(3)一般情况下，序列中各记录关键字的分布是随机的，因而可以认为快速排序算法的平均时间复杂度为O(nlog2n)。实验证明，当n较大时，快速排序是目前被认为最好的一种内部排序方法。 在算法实现中需设置一个栈的存贮空间来实现递归，栈的大小取决于递归深度，最多不会超过n。若每次都选较长的分组序列进
28、栈，而处理较短的分组序列，则递归深度最多不会超过log2n，因此快速排序需要的辅助存贮空间为O(log2n)。 快速排序算法是不稳定排序，对于有相同关键字的记录，排序后有可能颠倒位置。,2018/9/30,48,8.4选择排序,选择排序（Selection Sort）的基本思想是：不断从待排记录序列中选出关键字最小的记录插入已排序记录序列的后面，直到n个记录全部插入已排序记录序列中。本节主要介绍两种选择排序方法：简单选择排序和堆排序。,8.4.1 简单选择排序,简单选择排序(Simple Selection Sort)也称直接选择排序，是选择排序中最简单直观的一种方法。其基本操作思想：,(1)
29、每次从待排记录序列中选出关键字最小的记录； (2)将它与待排记录序列第一位置的记录交换后，再将其“插入”已排序记录序列(初始为空)；,2018/9/30,49,(3)不断重复过程(1)和(2)，就不断地从待排记录序列中剩下的(n-1，n-2，2)个记录中选出关键字最小的记录与该区第1位置的记录交换(该区第1个位置不断后移，该区记录逐渐减少)，然后把第1位置的记录不断 “插入” 已排序记录序列之后。经过n-1次的选择和多次交换后，R1 Rn就排成了有序序列，整个排序过程结束。具有n个记录的待排记录序列要做n-1次的选择和交换才能成为有序表。,简单选择排序算法描述如下：,2018/9/30,50,
30、void Select_Sort(RecType R,int n) int i,j,k; RecType temp; for(i=1;in;i+) /进行n-1趟排序，每趟选出1个最小记录 k=i; /假定起始位置为最小记录的位置 for(j=i+1;j=n;j+) /查找最小记录 if(Rj.keyn/2的结点Ri都,2018/9/30,57,没有孩子结点，因此以Ri为根的子树已经是堆。从i=n/2的结点Ri开始，比较根结点与左、右孩子的关键字值，若根结点的值大于左、右孩子中的较小者，则交换根结点和值较小孩子的位置，即把根结点下移，然后根结点继续和新的孩子结点比较，如此一层一层地递归下去，直到根结点下移到某一位置时，它的左、右子结点的值都大于它的值或者已成为叶子结点。这个过程称为“筛选”。从一个无序序列建堆的过程就是一个反复“筛选”的过程，“筛选”需要从i=n/2的结点Ri开始，直至结点R1结束。例如有一个8个元素的无序序列56,37,48,24,61,05,16,37，它所对应的完全二叉树及其建堆过程如图8-9所示。因为n=8，n/2=4，所以从第4个结点起至第一个结点止，依次对每一个结点进行“筛选”。,
