《排序的概念及种类.ppt》由会员分享，可在线阅读，更多相关《排序的概念及种类.ppt（107页珍藏版）》请在三一办公上搜索。
1、2023/10/7,1,第8章 排序,排序的概念及种类 插入法排序的各种具体实现方法及算法分析 选择法排序的各种具体方法的实现及时间性能分析 交换法排序的具体实现及性能分析 归并排序和基数排序的各自实现算法,传世 为您整理,2023/10/7,2,本章导读,排序是日常工作和软件设计中常用的运算之一。为了提高查询速度需要将无序序列按照一定的顺序组织成有序序列。由于需要排序的数据表的基本特性可能存在差异，使得排序方法也不同。如何合理地组织数据的逻辑顺序，按照何种方式排出的序列最有效？这是本章要讨论的主题。本章主要介绍排序的概念及几种最常见的排序方法，讨论其性能和特点，并在此基础上进一步讨论各种方法
2、的适用场合，以便在实际应用中能根据具体的问题选择合适的排序方法。通过本章学习，读者应该掌握以下几项内容：排序的概念及种类 插入法排序的各种具体实现方法及算法分析 选择法排序的各种具体方法的实现及时间性能分析 交换法排序的具体实现及性能分析 归并排序和基数排序的各自实现算法,2023/10/7,3,8.1 排序的基本概念,8.1.1 排序及其分类,1排序概念,排序（sorting）又称分类，是数据处理领域中一种很常用的运算。排序就是把一组记录或数据元素的无序序列按照某个关键字值（关键字）递增或递减的次序重新排列的过程。排序的主要目的就是实现快速查找。日常生活中通过排序以后进行检索的例子屡见不鲜。
3、如电话簿、病历、档案室中的档案、图书馆和各种词典的目录表等，几乎都需要对有序数据进行操作。,2023/10/7,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)这个将原有表中任意顺序的记录变成一个按关键字有序排列的过程称为排序。,2023/10/7,5,2排序分类,增排序和减排序：如果排序的结果是按关键字从小到大的次序排列的，就是增排序，否则就是减排序。稳定排序和
4、不稳定排序：假设Ki=Kj（1in，1jn，ij），且在排序前的序列中Ri领先于Rj（即ij）。若在排序后的排序中Ri仍领先于Rj，即那些具有相同关键字的记录，经过排序后它们的相对次序仍然保持不变，则称这种排序方法是稳定的；反之，若Rj领先于Ri，则称所用的方法是不稳定的。,2023/10/7,6,(3)内部排序与外部排序：在排序中，若数据表中的所有记录的排列过程都是在内存中进行的，称为内部排序。由于待排序的记录数量太多，在排序过程中不能同时把全部记录放在内存，需要不断地通过在内存和外存之间交换数据元素来完成整个排序的过程，称为外部排序。在外部排序情况下，只有部分记录进入内存，在内存中进行内部
5、排序，待排序完成后再交换到外部存储器中加以保存。然后再将其它待排序的记录调入内存继续排序。这一过程需要反复进行，直到全部记录排出次序为止。显然，内部排序是外部排序的基础，本章先介绍内部排序的各种方法，最后再讨论外部排序。,2023/10/7,7,8.1.2 排序算法的效率分析,与许多算法一样，对各种排序算法性能的评价主要从两个方面来考虑，一是时间性能；二是空间性能。,1 时间复杂度分析,排序算法的时间复杂度可用排序过程中记录之间关键字的比较次数与记录的移动次数来衡量。在本章各节中讨论算法的时间复杂度时，一般都按平均时间复杂度进行估算；对于那些受数据表中记录的初始排列及记录数目影响较大的算法，按
6、最好情况和最坏情况分别进行估算。,2023/10/7,8,2空间复杂度分析,排序算法的空间复杂度是指算法在执行时所需的附加存储空间，也就是用来临时存储数据的内存使用情况。在以后的排序算法中，若无特别说明，均假定待排序的记录序列采用顺序表结构来存储，即数组存储方式，并假定是按关键字递增方式排序。为简单起见，假设关键字类型为整型。待排序的顺序表类型的类型定义如下：typedef int KeyType/定义关键字类型 typedef struct dataType/记录类型 keytype key;/关键字项 elemtype otherelement;/其他数据项 RecType;,2023/1
7、0/7,9,8.2 插入排序,插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。也就是说，将待序列表分成左右两部分，左边为有序表（有序序列），右边为无序表（无序序列）。整个排序过程就是将右边无序表中的记录逐个插入到左边的有序表中，构成新的有序序列。根据不同的插入方法，插入排序算法主要包括：直接插入排序、折半插入排序、表插入排序和希尔排序等。本章重点介绍直接插入排序、折半插入排序和希尔排序。,2023/10/7,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的插入后，整个序列排序完毕。,2023/10/7,11,向有序表中插入记录，主
9、要完成如下操作：(1)搜索插入位置。(2)移动插入点及其以后的记录空出插入位置。(3)插入记录。,假设将n个待排序的记录顺序存放在长度为n+1的数组R1Rn 中。R0作为辅助空间，用来暂时存储需要插入的记录，起监视哨的作用。直接插入排序算法如下:,2023/10/7,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)/搜索插入位置并后移腾出空 Rj+1=Rj;j-;Rj+1=R
10、0;/插入元素,2023/10/7,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的插入排序。如此不断进行，直到完成记录Rn的插入排序，整个序列变成按关键字非递减的有序序列为
11、止。在搜索插入位置的过程中，R0.key与Ri-j.key进行比较时，如果j=i，则循环条件 R0.keyRi-j.key不成立，从而退出while 循环。由此可见R0起到了监视哨的作用，避免了数组下标的出界。,2023/10/7,14,【例8-1】假设有7个待排序的记录，它们的关键字分别为23，4，15，8，19，24，15，用直接插入法进行排序。,【解】直接插入排序过程如图8-1所示。方括号 中为已排好序的记录的关键字，有两个记录的关键字都为15，为表示区别，将后一个15加下划线。,图8-1 直接插入排序,2023/10/7,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、。,2023/10/7,16,（2）当初始数据序列的关键字序列是递减排列时，这是最坏的情况。在第i次排序时，while语句内的循环体执行次数为i。因此，关键字的比较次数为i，而移动次数为i+1。所以，整个排序过程中的比较次数和移动次数分别为：,（3）一般情况下，可认为出现各种排列的概率相同，因此取上述两种情况的平均值，作为直接插入排序关键字的比较次数和记录移动次数，约为n2/4。所以其时间复杂度为O(n2)。根据上述分析得知：当原始序列越接近有序时，该算法的执行效率就越高。,2023/10/7,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比较，经过一次比较，便可排除一半记录，把可插入的区间缩小一半，故称为折半。,2023/10/7,18,设置始指针low，指向有序表的第一
15、个记录，尾指针high，指向有序表的最后一个记录，中间指针mid指向有序表中间位置的记录。每次将待插入记录的关键字与mid位置记录的关键字进行比较，从而确定待插入记录的插入位置。折半插入排序算法如下：,typedef int keytype;void Insert_halfSort(RecType R,int n)/*对顺序表R作折半插入排序*/int i,j,low,high,mid;for(i=2;i=n;i+)R0=Ri;/保存待插入元素 low=1;high=i-1;/设置初始区间,2023/10/7,19,while(lowRmid.key)low=mid+1;插入位置在后半部分中
16、else high=mid-1;/插入位置在前半部分中 for(j=i-1;j=high+1;-j)/high+1为插入位置 Rj+1=Rj;/后移元素，空出插入位置 Rhigh+1=R0;/将元素插入,2023/10/7,20,【例8-2】待排序记录的关键字为：28，13，72，85，39，41，6，20，在前7个记录都已排好序的基础上，采用折半插入第8个记录的比较过程如图8-2所示。,图8-2 折半插入排序,2023/10/7,21,折半插入排序的比较次数与待排序记录的初始排列次序无关，仅依赖于记录的个数。插入第i个元素时，如果i=2j（1jlog2n），则无论关键字值的大小，都恰好经过j
17、=log2i次比较才能确定其应插入的位置；如果2ji2j+1，则比较次数为j+1。因此将n个记录（设n=2k）排序的总比较次数为：,2023/10/7,22,折半插入排序仅减少了关键字间的比较次数，但记录的移动次数不变。因此折半插入排序的时间复杂度仍为O(n2)。折半插入排序的空间复杂度与直接插入排序相同。折半插入排序也是一个稳定的排序方法。,2023/10/7,23,8.2.3 希尔排序,希尔排序（shells sort）又称缩小增量排序(Diminishing Increment Sort)。它是希尔（D.L.Shell）于1959年提出的插入排序的改进算法。如前所述，直接插入排序算法的时
18、间性能取决于数据的初始特性，一般情况下，它的时间复杂度为O(n2)。但是当待排序列为正序或基本有序时，时间复杂度则为O(n)。因此，若能在一次排序前将排序序列调整为基本有序，则排序的效率就会大大提高。正是基于这样的考虑，希尔提出了改进的插入排序方法。希尔排序的基本思想是：先将整个待排记录序列分割成若干小组（子序列），分别在组内进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。希尔排序的具体步骤如下：,2023/10/7,24,（1）首先取一个整数d1n，称之为增量，将待排序的记录分成d1个组，凡是距离为d1倍数的记录都放在同一个组，在各组内进行直接插入排序，
19、这样的一次分组和排序过程称为一趟希尔排序。（2）再设置另一个新的增量d2d1，采用与上述相同的方法继续进行分组和排序过程。（3）继续取di+1di，重复步骤(2)，直到增量d=1，即所有记录都放在同一个组中。,【例8-3】设有一个待排序的序列有10个记录，它们的关键字分别为58，46，72，95，84，25，37，58，63，12，用希尔排序法进行排序。【解】图8-3给出了希尔排序的整个过程，用同一连线上的关键字表示其所属的记录在同一组。为区别具有相同关键字58的不同记录，用下划线标记后一个记录的关键字。,2023/10/7,25,图8-3 希尔排序过程,2023/10/7,26,第一趟排序时
20、，取d1=5，整个序列被划分成5组，分别为58，25，46，37，72，58，95，63，84，12。对各组内的记录进行直接插入排序，得到第一趟排序结果如图8-3(a)所示。第二趟排序时，取d2=3，将第一趟排序的结果分成3组，分别为25，63，46，84,37，12，72,58，58，95。再对各组内记录进行直接插入排序，得到第二趟排序结果如图8-3(b)所示。25 12 58 46 37 58 63 72 95 84第三趟排序时，取d3=1，所有的数据记录分成1组25，12，58，46，37，58，63，72，95，84，此时序列基本“有序”，对其进行直接插入排序，最后得到希尔排序的结果如
21、图8-3(c)所示。12 25 37 46 58 58 63 72 86 95。,2023/10/7,27,希尔排序的算法如下：void Shell_Sort(RecType R,int n)int i,j,d;RecType temp;d=n2;/初始增量 while(d0)/通过增量控制排序的执行过程 for(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,2023/10/7,28,从希尔排序过程可以看到：（1）算法中约定初始增量d1为已知；（2）
22、算法中采用简单的取增量值的方法，从第二次起取增量值为其前次增量值的一半。在实际应用中，可能有多种取增量的方法，并且不同的取值方法对算法的时间性能有一定的影响，因而一种好的取增量的方法是改进希尔排序算法时间性能的关键。（3）希尔排序开始时增量较大，分组较多，每组的记录数较少，故各组内直接插入过程较快。随着每一趟中增量di逐渐缩小，分组数逐渐减少，虽各组的记录数目逐渐增多，但由于已经按di-1作为增量排过序，使序列表较接近有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。希尔排序的时间复杂度约为O(n1.3)，它实际所需的时间取决于各次排序时增量的取值。大量研
23、究证明，若增量序列取值较合理，希尔排序时关键字比较次数和记录移动次数约为O(nlog2n)2。由于其时间复杂度分析较复杂，在此不做讨论。希尔排序会使关键字相同的记录交换相对位置，所以希尔排序是不稳定的。,2023/10/7,29,8.3交换排序,利用交换记录的位置进行排序的方法称为交换排序。其基本思想是：两两比较待排序记录的关键字，如果逆序就进行交换，直到所有记录都排好序为止。常用的交换排序方法主要有冒泡排序和快速排序。快速排序是一种分区交换排序法，是对冒泡排序方法的改进。,2023/10/7,30,冒泡排序（Bubble sort）的算法思想是：设待排序有n个记录，首先将第一个记录的关键字R
24、1.key和第二个记录的关键字R2.key进行比较，若R1.keyR2.key，就交换记录R1和R2在序列中的位置；然后继续对R2.key和R3.key进行比较，并作相同的处理；重复此过程，直到关键字Rn-1.key和Rn.key比较完成。其结果是n个记录中关键字最大的记录被交换到序列的最后一个记录的位置上，即具有最大关键字的记录被“沉”到了最后，这个过程被称为一趟冒泡排序。然后进行第二趟冒泡排序，对序列表中前n-1个记录进行同样的操作，使序列表中关键字次大的记录被交换到序列的n-1位置上；第i趟冒泡排序是从R1到Rn-i+1依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这
25、n-i+1个记录中关,8.3.1 冒泡排序,2023/10/7,31,键字最大的记录被交换到n-i+1位置上。每一趟排序都有一个相对大的数据被交换到后面，就像一块块“大”石头不断往下沉，最大的总是最早沉下；而具有较小关键字的记录则不断向上（前）移动位置，就像水中的气泡逐渐向上飘浮一样，冒到最上面的是关键字值最小的记录。所以把这种排序方法称为冒泡排序。对有n个记录的序列最多做n-1趟冒泡就会把所有记录依关键字大小排好序。如果在某一趟排序中都没有发生相邻记录的交换，表示在该趟之前已达到排序的目的，整个排序过程可以结束。在操作实现时，常用一个标志位flag标示在第i趟是否发生了交换，若在第i趟发生过
26、交换，则置flag=false（或0）；若第i趟没有发生交换，则置flag=true（或1），表示在第i-1趟已经达到排序目的，可结束整个排序过程。,2023/10/7,32,算法描述如下：#define False 0#define True 1typedef int keytype;void 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.keyRj.key)flag=0;/如果有逆
27、序的则置flag=0 R0=Rj;Rj=Rj+1;Rj+1=R0;if(flag=1)return;/flag为True则表示序列已有序，可结束排序过程,2023/10/7,33,在该算法中，外层循环控制排序的执行趟数，内层循环用于控制在一趟冒泡排序中相邻记录间的比较和交换。,【例8-4】假设有8个记录，关键字分别为53，38，47，24，69，05，17，38，用冒泡排序方法排序。,【解】冒泡排序过程如图8-4所示。,2023/10/7,34,图8-4 冒泡排序过程,2023/10/7,35,执行了5趟冒泡排序后，完成了整个排序过程。排序中当关键字间的比较呈逆序时，需要交换两个记录的位置，使
28、用一个辅助空间来完成交换。在算法中用数组中的R0作为辅助空间，所以其空间复杂度为O(1)。,对于有n个记录的待排序列进行冒泡排序，算法的时间复杂度依赖于待排序序列的初始特性，有以下几种情况：（1）如果初始记录序列为“正序”序列，则只需进行一趟排序，记录移动次数为0，关键字间比较次数为n-1；,2023/10/7,36,（2）如果初始记录序列为“逆序”序列，则进行n-1趟排序，每一趟中的比较和交换次数将达到最大，即冒泡排序的最大比较次数为=n(n-1)/2，最大移动次数为3=3n(n-1)/2。（3）一般情况下，比较次数n(n-1)/2，移动次数3n(n-1)/2，因此时间复杂度为O(n2)。由
29、相邻两个记录的交换条件可知冒泡排序是稳定排序。,2023/10/7,37,8.3.3 快速排序,快速排序（Quick Sorting）又称分区交换排序，是对冒泡排序算法的改进，是一种基于分组进行互换的排序方法。1快速排序的基本思想 快速排序的基本思想是：从待排记录序列中任取一个记录Ri作为基准（通常取序列中的第一个记录），将所有记录分成两个序列分组，使排在Ri之前的序列分组的记录关键字都小于等于基准记录的关键字值Ri.key，排在Ri之后的序列分组的记录关键字都大于Ri.key，形成以Ri为分界的两个分组，此时基准记录Ri的位置就是它的最终排序位置。此趟排序称为第一趟快速排序。然后分别对两个序
30、列分组重复上述过程，直到所有记录排在相应的位置上。,2023/10/7,38,2选取基准在快速排序中，选取基准常用的方法有：（1）选取序列中第一个记录的关键字值作为基准关键字。这种选择方法简单。但是当序列中的记录已基本有序时，这种选择往往使两个序列分组的长度不均匀，不能改进排序的时间性能。（2）选取序列中间位置记录的关键字值作为基准关键字。（3）比较序列中始端、终端及中间位置上记录的关键字值，并取这三个值中居中的一个作为基准关键字。为了叙述方便，在下面的快速排序中，选取第一个记录的关键字作为基准关键字。,2023/10/7,39,3快速排序的实现 算法中记录的比较和交换是从待排记录序列的两端向
31、中间进行的。设置两个变量i和j，其初值分别是n个待排序记录中第一个记录的位置号和最后一个记录的位置号。在扫描过程中，变量i，j的值始终表示当前所扫描分组序列的第一个和最后一个记录的位置号。将第一个记录R0作为基准记录放到一个临时变量temp中，将R0的位置空出。每趟快速排序，如下进行：（1）从序列最后位置的记录Rj开始依次往前扫描，若存在tempRj.key，则令j前移一个位置，即j=j-1，如此直到tempRj.key或i=j为止。若ij，则将记录Rj放入Ri 空出的位置（由变量i指示的位置）。此时Rj位置空出（由变量j指示的位置）。,2023/10/7,40,（2）从序列最前位置的记录Ri
32、开始依次往后扫描，若存在tempRi.key，则令i后移一个位置，即i=i+1，如此比较直到tempRi.key或i=j为止。若ij，则将记录Ri放入Rj 空出的位置（由变量j指示的位置）。此时Ri位置空出（用变量i指示的位置）。使j=j-1，继续进行步骤（1）的操作，即再从变量j所指示的当前位置依次向前比较交换。在一趟快速排序中，整个过程交替地从后往前扫描关键字值小的记录和从前往后扫描关键字值大的记录并放置到对应端空出的位置中，又空出新的位置。当从两个方向的扫描重合时，即i=j，就找到了基准记录的存放位置。按照快速排序的基本思想，在一趟快速排序之后，需要重复(1)，(2)，直到找到所有记录的
33、相应位置。显然，快速排序是一个递归的过程。,2023/10/7,41,算法描述如下：void Quick_Sort(RecType R,int left,int right)/用递归方法把Rleft至Rrigh的记录进行快速排序 int i=left,j=right,k;RecType temp;if(lefti/对基准后面的记录序列进行递归排序,2023/10/7,42,【例8-5】假设有8个记录，关键字的初始序列为45,34,67,95,78,12,26,45，用快速排序法进行排序。【解】（1）一趟快速排序过程如图8-5所示：,图8-5 一趟快速排序过程,2023/10/7,43,选取第一
34、个记录作为基准记录，存入临时单元temp中，腾出第一个位置（由i指示）。首先将temp中的45与Rj.key(45)相比较，因tempRj.key，j前移，即j=j-1；temp继续与Rj.key(26)比较，4526，进行第一次调整，将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交替地从两端向中间扫描以及记录位置的调整，当执行到i=j=4 时，一趟排序成功，将temp保存的记录放入该位置，这也
35、是该记录的最终排序位置。,2023/10/7,44,（2）各趟排序之后的结果,图8-6 快速排序过程,2023/10/7,45,快速排序算法的执行时间取决于基准记录的选择。一趟快速排序算法的时间复杂度为O(n)。下面分几种情况讨论整个快速排序算法需要排序的趟数：（1）在理想情况下，每次排序时所选取的记录关键字值都是当前待排序列中的“中值”记录，那么该记录的排序终止位置应在该序列的中间，这样就把原来的子序列分解成了两个长度大致相等的更小的子序列，在这种情况下，排序的速度最快。设完成n个记录待排序列所需的比较次数为C(n),则有：C(n)n+2C(n/2)2n+4C(n/4)kn+nC(1)(k是
36、序列的分解次数)若n为2的幂次值且每次分解都是等长的，则分解过程可用一棵满二叉树描述，分解次数等于树的深度k=log2n，因此有：C(n)nlog2n+nC(1)=O(nlog2n)整个算法的时间复杂度为O(nlog2n)。,2023/10/7,46,(2)在极端情况下，即每次选取的“基准”都是当前分组序列中关键字最小(或最大)的值，划分的结果是基准的前边(或右边)为空，即把原来的分组序列分解成一个空序列和一个长度为原来序列长度减1的子序列。总的比较次数达到最大值：,如果初始记录序列已为升序或降序排列，并且选取的基准记录又是该序列中的最大或最小值，这时的快速排序就变成了“慢速排序”。整个算法的
37、时间复杂度为O(n2)。为了避免这种情况的发生，可修改上面的排序算法，在每趟排序之前比较当前序列的第一、最后和中间记录的关键字，取关键字居中的一个记录作为基准值调换到第一个记录的位置。,2023/10/7,47,(3)一般情况下，序列中各记录关键字的分布是随机的，因而可以认为快速排序算法的平均时间复杂度为O(nlog2n)。实验证明，当n较大时，快速排序是目前被认为最好的一种内部排序方法。在算法实现中需设置一个栈的存贮空间来实现递归，栈的大小取决于递归深度，最多不会超过n。若每次都选较长的分组序列进栈，而处理较短的分组序列，则递归深度最多不会超过log2n，因此快速排序需要的辅助存贮空间为O(
38、log2n)。快速排序算法是不稳定排序，对于有相同关键字的记录，排序后有可能颠倒位置。,2023/10/7,48,8.4选择排序,选择排序（Selection Sort）的基本思想是：不断从待排记录序列中选出关键字最小的记录插入已排序记录序列的后面，直到n个记录全部插入已排序记录序列中。本节主要介绍两种选择排序方法：简单选择排序和堆排序。,简单选择排序,简单选择排序(Simple Selection Sort)也称直接选择排序，是选择排序中最简单直观的一种方法。其基本操作思想：,(1)每次从待排记录序列中选出关键字最小的记录；(2)将它与待排记录序列第一位置的记录交换后，再将其“插入”已排序记
39、录序列(初始为空)；,2023/10/7,49,(3)不断重复过程(1)和(2)，就不断地从待排记录序列中剩下的(n-1，n-2，2)个记录中选出关键字最小的记录与该区第1位置的记录交换(该区第1个位置不断后移，该区记录逐渐减少)，然后把第1位置的记录不断“插入”已排序记录序列之后。经过n-1次的选择和多次交换后，R1 Rn就排成了有序序列，整个排序过程结束。具有n个记录的待排记录序列要做n-1次的选择和交换才能成为有序表。,简单选择排序算法描述如下：,2023/10/7,50,void Select_Sort(RecType R,int n)int i,j,k;RecType temp;fo
40、r(i=1;in;i+)/进行n-1趟排序，每趟选出1个最小记录 k=i;/假定起始位置为最小记录的位置 for(j=i+1;j=n;j+)/查找最小记录 if(Rj.keyRk.key)k=j;if(i!=k)/如果k不是假定位置，则交换 temp=Rk;/交换记录 Rk=Ri;Ri=temp;,本算法中有两重循环：外循环用于控制排序的次数，内循环用于查找当前待排记录序列中关键字最小的记录。,2023/10/7,51,【例8-6】采用简单选择排序对以下6个记录进行排序【解】图8-7是简单选择排序的过程示意图。图中 中的数据表示待排记录序列的关键字。,图8-7 简单选择排序示例,2023/10
41、/7,52,简单选择排序算法的关键字比较次数与记录的初始排列无关。假定整个序列表有n个记录，总共需要n-1趟的选择；第i(i=1，2，n-1)趟选择具有最小关键字记录所需要的比较次数是n-i-1次，总的关键字比较次数为：比较次数=(n-1)+(n-2)+1=n(n-1)/2 而记录的移动次数与其初始排列有关。当这组记录的初始状态是按关键字从小到大有序时，每一趟选择后都不需要进行交换，记录的总移动次数为0，这是最好的情况；而最坏的情况是每一趟选择后都要进行交换，一趟交换需要移动记录3次。总的记录移动次数为3(n-1)。所以，简单选择排序的时间复杂度为O(n2)。简单选择排序算法只需要一个临时单元
42、用作交换，因此空间复杂度为O(1)。由于在直接选择排序过程中存在不相邻记录之间的互换，可能会改变具有相同关键字记录的相对位置，所以该算法是不稳定排序。,2023/10/7,53,8.4.2 堆排序,堆排序(Heap Sort)借助于完全二叉树结构进行排序，是一种树型选择排序。在直接选择排序时，为从n个关键字中选出最小值，需要进行n-1次比较，然后又在剩下的n-1个关键字中选出次最小值，需要n-2次比较。在n-2次的比较中可能有许多比较在前面的n-1次比较中已经做过，因此存在多次重复比较，降低了算法的效率。堆排序方法是由J.Williams和Floyd提出的一种改进方法，它在选择当前最小关键字记
43、录的同时，还保存了本次排序过程所产生的比较信息。,2023/10/7,54,n个元素序列k1，k2，kn，当且仅当满足如下性质称为堆。(1)这些元素是一棵完全二叉树中的结点，且对于i=1，2，,n，ki是该完全二叉树中编号为i的结点；(2)kik2i（或kik2i）(1in/2)(3)kik2i+1(或 kik2i+l)(1in/2)从堆的定义可以看出，堆是一棵完全二叉树，其中每一个非终端结点的元素均大于等于（或小于等于）其左、右孩子结点的元素值。图8-8(a)和 图8-8(b)为堆的两个示例，所对应的元素序列分别为92,84,25,36,14,07和15,39,23,87,44,31,52,
44、90。,1堆的定义,2023/10/7,55,根据堆的定义，可以推出堆的两个性质：堆的根结点是堆中元素值最小（或最大）的结点，称为堆顶元素。从根结点到每个叶结点的路径上，元素的排序序列都是递减（或递增）有序的。,（a）堆顶元素值最大,（b）堆顶元素值最小,图8-8 堆的示例,2023/10/7,56,2.堆的构建,堆排序的基本思想是：对一组待排序记录，首先把它们的关键字按堆定义排列成一个序列（称为初始建堆），堆顶元素为最小关键字的记录，将堆顶元素输出；然后对剩余的记录再建堆，得到次最小关键字记录；如此反复进行，直到全部记录有序为止，这个过程称为堆排序。如何将一个无序序列建成一个堆？具体做法是：
45、把待排序记录存放在数组R1.n之中，将R看作一棵二叉树，每个结点表示一个记录，将第一个记录R1作为二叉树的根，以下各记录R2.n依次逐层从左到右顺序排列，构成一棵完全二叉树，任意结点Ri的左孩子是R2i，右孩子是R2i+1，双亲是Ri/2。将待排序的所有记录放到一棵完全二叉树的各个结点中（注意：这时的完全二叉树并不具备堆的特征）。此时所有in/2的结点Ri都,2023/10/7,57,没有孩子结点，因此以Ri为根的子树已经是堆。从i=n/2的结点Ri开始，比较根结点与左、右孩子的关键字值，若根结点的值大于左、右孩子中的较小者，则交换根结点和值较小孩子的位置，即把根结点下移，然后根结点继续和新的
46、孩子结点比较，如此一层一层地递归下去，直到根结点下移到某一位置时，它的左、右子结点的值都大于它的值或者已成为叶子结点。这个过程称为“筛选”。从一个无序序列建堆的过程就是一个反复“筛选”的过程，“筛选”需要从i=n/2的结点Ri开始，直至结点R1结束。例如有一个8个元素的无序序列56,37,48,24,61,05,16,37，它所对应的完全二叉树及其建堆过程如图8-9所示。因为n=8，n/2=4，所以从第4个结点起至第一个结点止，依次对每一个结点进行“筛选”。,2023/10/7,58,(a)2437不调整,(b)4805 48沿左子树下,移一层,图8-9 建堆过程示例,2023/10/7,59
47、,(对i=4的结点筛选),(对i=3的结点筛选),(c)3724 37沿左子树下移一层,(d)5605 56沿右子树下移一层,(对i=2的结点筛选),(对i=1的结点筛选),(e)5616 56沿右子树继续下移一层,(f)比较调整结束 堆建好,2023/10/7,60,筛选算法描述如下：void Sift(RecType R,int k,int n)/k表示被筛选的结点的关键字，n表示待排序的记录个数 int i,j;i=k;j=2*i;/计算Ri的左孩子位置 R0=Ri;/将Ri保存在临时单元中 while(jRj+1.key)+j;/选择左右孩子中最小者 if(R0.keyRj.key)/
48、当前结点大于左右孩子的最小者 Ri=Rj;i=j;j=2*i;else/当前结点不大于左右孩子 break;Ri=R0;/被筛选结点放到最终合适的位置上,2023/10/7,61,建初始堆的过程描述为：for(i=n/2;i0;-i)Sift(R,i,n);在输出堆顶记录之后，如何调整剩余记录成为一个新的堆？由堆的定义可知，在输出堆顶记录之后，以根结点的左、右孩子为根的子树仍然为堆。为了把剩余的记录建成一个新堆，可以将堆的最后一个记录放到堆顶位置作为根结点，形成一个新的完全二叉树。该完全二叉树不是一个堆，但根结点的左右子树均为根。此时，只需将根结点由上至下“筛选”到合适的位置，使它的左、右孩子
49、的关键字值都大于它的值，至此就完成了新堆的建立。建新堆的过程描述为：for(j=n;j1;-j)R0=R1;R1=Rj;Rj=R0;Sift(R,l,j-1);,2023/10/7,62,3堆排序,对于已建好的堆，可以采用下面两个步骤进行排序：(1)输出堆顶元素：将堆顶元素（第一个记录）与当前堆的最后一个记录对调。(2)调整堆：将输出根结点之后的新完全二叉树调整为堆。不断地输出堆顶元素，又不断地把剩余的元素建成新堆，直到所有的记录都变成堆顶元素输出。堆排序的算法描述如下：void Heap_Sort(RecType R,int n)int j;for(j=n/2;j0;-j)/建初始堆Sift
50、(R,j,n);for(j=n;j1;-j)/进行n-1趟排序 R0=R1;/将堆顶元素与堆中最后一个元素交换R1=Rj;Rj=R0;Sift(R,l,j-1);/将R1Rj-1调整为堆,2023/10/7,63,【例8-7】用“筛选法”在如图8-9(f)的堆中进行排序。【解】调用筛选运算进行堆排序的过程如图8-10(a)(n)所示。,（a）初始堆,（b）交换05和37,（c）重建堆，筛选37下移一层,（d）交换16和56,2023/10/7,64,（e）重建堆，筛选56下移两层,（f）交换24和48,（g）重建堆，筛选48下移一层,（h）交换37和61,2023/10/7,65,（i）重建堆
