1、第第8 8章章 排序排序2022年8月3日星期三本章概述本章概述 排序是计算机程序设计中的一种重要操作，它是对排序是计算机程序设计中的一种重要操作，它是对数据元素序列建立某种有序排列的过程。有序的表或文数据元素序列建立某种有序排列的过程。有序的表或文件便于查找，如有序的顺序表可以采用效率较高的折半件便于查找，如有序的顺序表可以采用效率较高的折半查找法，而无序的顺序表则只能采用效率较低的顺序查查找法，而无序的顺序表则只能采用效率较低的顺序查找法，又如建造树表本身也是一个排序的过程。所以，找法，又如建造树表本身也是一个排序的过程。所以，对各种排序方法的学习和研究，尤其是高效地排序，是对各种排序方法
2、的学习和研究，尤其是高效地排序，是计算机应用的一个重要课题。计算机应用的一个重要课题。2022年8月3日星期三8.18.1 基本概念基本概念 排序排序(sorting)(sorting)是计算机程序设计中的一种重要操作，是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。排列成一个按关键字有序的序列。1.1.排序的定义排序的定义 假设含假设含n n个记录的序列为：个记录的序列为：RR1 1,R,R2 2,R,Rn n(8-1)(8-1)其相应的关键字序列为：其相应的关键字序列为：KK
3、1 1,K,K2 2,K,Kn n 2022年8月3日星期三 需确定需确定1,2,n1,2,n的一种排列的一种排列p p1 1,p,p2 2,p,pn n,使其相应使其相应的关键字满足如下的非递减（或非递增）关系的关键字满足如下的非递减（或非递增）关系KpKp1 1 Kp Kp2 2 Kp Kpn n 即使（即使（8-18-1）的序列成为一个按关键字有序的排列）的序列成为一个按关键字有序的排列Rp1,RpRp1,Rp2 2,Rp,Rpn n 这样的一种操作称为排序。这样的一种操作称为排序。2022年8月3日星期三2.2.稳定排序法与非稳定排序法稳定排序法与非稳定排序法关键字：一个记录中可以标识
4、该数据项的值。关键字：一个记录中可以标识该数据项的值。关键字分主关键字和次关键字两种。关键字分主关键字和次关键字两种。主关键字：数据元素值不同时该关键字的值也一定不同。主关键字：数据元素值不同时该关键字的值也一定不同。主关键字是能够唯一区分各个不同数据元素的关键字。主关键字是能够唯一区分各个不同数据元素的关键字。不满足主关键字定义的关键字称为次关键字。不满足主关键字定义的关键字称为次关键字。2022年8月3日星期三 3.3.内部排序与外部排序内部排序与外部排序 根据排序过程中涉及的存储器不同，可将排序方法分根据排序过程中涉及的存储器不同，可将排序方法分为两大类：为两大类：(1)(1)内部排序：
5、指待排序记录存放在计算机随机存储内部排序：指待排序记录存放在计算机随机存储器中进行排序的过程。器中进行排序的过程。(2)(2)外部排序：指待排序记录的数量很大，以致于内存外部排序：指待排序记录的数量很大，以致于内存一次不能容纳全部记录，在排序的过程中尚需对外存一次不能容纳全部记录，在排序的过程中尚需对外存进行访问的排序过程。进行访问的排序过程。2022年8月3日星期三 按排按排序依据的原则不同序依据的原则不同，可将内部排序大致可分为：，可将内部排序大致可分为：插入排序、交换排序、选择排序、归并排序、基数排序插入排序、交换排序、选择排序、归并排序、基数排序五类。五类。按内部排序过程中所需的工作量
6、来区分，可分为以按内部排序过程中所需的工作量来区分，可分为以下下3 3类：类：(1)(1)简单的排序方法，其时间复杂度为简单的排序方法，其时间复杂度为O(nO(n2 2)。(2)(2)先进的排序方法先进的排序方法,其时间复杂度为其时间复杂度为O(nlogn)O(nlogn)。(3)(3)基数排序方法，其时间复杂度为基数排序方法，其时间复杂度为O(dO(dn)n)。2022年8月3日星期三 外部外部排序的方法主要是多路平衡归并的实现。在排序的方法主要是多路平衡归并的实现。在排序过程中需要进行如下两种基本操作排序过程中需要进行如下两种基本操作：(1)(1)比较两个关键字的大小比较两个关键字的大小。
7、(2)(2)将记录从一个位置移动到另一个位置将记录从一个位置移动到另一个位置。2022年8月3日星期三 4.4.待排序记录的存储方式待排序记录的存储方式 待排序记录可有以下待排序记录可有以下3 3种存储方式：种存储方式：(1)(1)待排序的一组记录存放在地址连续的一组存储单元上。待排序的一组记录存放在地址连续的一组存储单元上。记录之间的次序关系由其存储位置决定，实现排序必须移记录之间的次序关系由其存储位置决定，实现排序必须移动记录。动记录。(2)(2)一组待排序记录存放在静态链表中，记录之间的次序一组待排序记录存放在静态链表中，记录之间的次序关系由指针指示，则实现排序不需要移动记录，仅需修改关
8、系由指针指示，则实现排序不需要移动记录，仅需修改指针即可。这种存储方式下实现的排序又称链表排序。指针即可。这种存储方式下实现的排序又称链表排序。2022年8月3日星期三(3)(3)待排序记录本身存储在一组地址连续的存储单待排序记录本身存储在一组地址连续的存储单元内，同时另设一个指示各个记录存储位置的地址元内，同时另设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量，在排序过程中不移动记录本身，而移动地址向量中的这些记录的向量中的这些记录的“地址地址”，在排序结束后再按，在排序结束后再按照地址向量中的值调整记录的存储位置。这种存储照地址向量中的值调整记录的存储位置。
9、这种存储方式下实现的排序又称地址排序。方式下实现的排序又称地址排序。2022年8月3日星期三 本章连续的存储待排序记录，设关键字为整型。定本章连续的存储待排序记录，设关键字为整型。定义如下：义如下：#define MAXSIZE 20#define MAXSIZE 20/存储空间的最大值存储空间的最大值typedef int KeyTypetypedef int KeyType;/定义关键字类型为整型定义关键字类型为整型typedef structtypedef struct KeyTypeKeyType key;key;/关键字域关键字域InfoType otherinfoInfoType
10、otherinfo;/其他数据项其他数据项 RedType RedType;/记录类型记录类型 typedef structtypedef struct RedTypeRedType rMAXSIZE+1;rMAXSIZE+1;/r0/r0闲置或用作监视哨单元闲置或用作监视哨单元intint length;length;/顺序表长度顺序表长度 SqList SqList;/顺序表类型顺序表类型2022年8月3日星期三8.2 8.2 插入排序插入排序 插入排序的基本思想：插入排序的基本思想：从初始有序的子集合开始，不断地把新的数据元从初始有序的子集合开始，不断地把新的数据元素插入到已排列有序的子
11、集合的合适位置上，使子集素插入到已排列有序的子集合的合适位置上，使子集合中数据元素的个数不断增多，当子集合等于集合时，合中数据元素的个数不断增多，当子集合等于集合时，插入排序算法结束。常用的插入排序方法有直接插入插入排序算法结束。常用的插入排序方法有直接插入排序、折半插入排序、表插入排序和希尔排序。排序、折半插入排序、表插入排序和希尔排序。本节介绍直接插入排序和希尔排序两种插入排序本节介绍直接插入排序和希尔排序两种插入排序方法。方法。2022年8月3日星期三 直接插入排序（直接插入排序（straight insertion sortstraight insertion sort）的基）的基本思
12、想：本思想：每次只考虑一个待排序的元素，用这个元素同已每次只考虑一个待排序的元素，用这个元素同已经排序好的其他元素逐一进行比较，在找到适当的位经排序好的其他元素逐一进行比较，在找到适当的位置后，将此元素插入，从而得到一个新的有序表，然置后，将此元素插入，从而得到一个新的有序表，然后再选择下一个待排序的元素。后再选择下一个待排序的元素。8.2.1 8.2.1 直接插入排序直接插入排序2022年8月3日星期三 【例【例8-18-1】已知一组待排序的记录的初始序列为已知一组待排序的记录的初始序列为36,36,45,60,92,78,12,25,4545,60,92,78,12,25,45，用直接插入
13、排序法对其，用直接插入排序法对其进行排序。进行排序。算法思想：算法思想：前前4 4个记录已按关键字递增的排序，构成含有个记录已按关键字递增的排序，构成含有4 4个记录个记录的有序序列的有序序列36,45,60,9236,45,60,92。现将关键字为。现将关键字为7878的第的第5 5个记录个记录插入其中，形成新的有序序列，首先在有序序列中进行查插入其中，形成新的有序序列，首先在有序序列中进行查找比较。找比较。2022年8月3日星期三 确定插入位置。假设从右向左依次比较，由于确定插入位置。假设从右向左依次比较，由于6078926078ni n，则排序完成，否则转到，则排序完成，否则转到(4)(
14、4)。2022年8月3日星期三 执行具体过程如算法执行具体过程如算法8.18.1所示。所示。void InsertSort(SqListvoid InsertSort(SqList&L)&L)/对顺序表对顺序表L L进行直接插入排序进行直接插入排序for(i=2;i=L.length;+ifor(i=2;i=L.length;+i)if(L.ri.keyif(L.ri.keyL.ri-1.key)L.ri-1.key)/需将需将L.riL.ri 插入有序表插入有序表L.r0=L.riL.r0=L.ri;/制为哨兵制为哨兵for(j=i-1;L.r0.keyL.rj.key;-jfor(j=i-
15、1;L.r0.keyL.rj.key;-j)L.rj+1=L.rjL.rj+1=L.rj;/记录后移记录后移L.rj+1=L.r0;L.rj+1=L.r0;/插入到正确位置插入到正确位置/InserSort/InserSort算法算法8.18.12022年8月3日星期三 【例【例8-18-1】中直接插入排序的过程如下图所示，图中】中直接插入排序的过程如下图所示，图中用箭头指明相应的数据元素在排序过程中的位置变化，用箭头指明相应的数据元素在排序过程中的位置变化，同时为了检测稳定性，在后一个同时为了检测稳定性，在后一个“45”45”上加上了上加上了“”符号。符号。2022年8月3日星期三 算法分析
16、：算法分析：直接插入排序算法的时间复杂度分析可分最好、直接插入排序算法的时间复杂度分析可分最好、最坏和平均三种情况来考虑。最坏和平均三种情况来考虑。(1)(1)最好的情况：原始数据元素集合已全部排好序。最好的情况：原始数据元素集合已全部排好序。这时算法中内层这时算法中内层forfor循环的循环次数每次均为循环的循环次数每次均为0 0。这样，。这样，外层外层forfor循环中每次数据元素的比较次数均为循环中每次数据元素的比较次数均为1 1。因此，。因此，整个排序过程中的比较次数为整个排序过程中的比较次数为n-1n-1，没有赋值操作。所，没有赋值操作。所以直接插入排序算法最好情况下的时间复杂度为以
17、直接插入排序算法最好情况下的时间复杂度为O(nO(n)。2022年8月3日星期三 (2)(2)最坏的情况：原始数据元素集合为反序排列。时最坏的情况：原始数据元素集合为反序排列。时间复杂度为间复杂度为O(nO(n2 2)。在反序情况下，由于第。在反序情况下，由于第i i个记录找到个记录找到相应插入位置需要比较相应插入位置需要比较i i次，所以从第次，所以从第2 2到第到第n n个记录共个记录共需比较的总次数为：需比较的总次数为：每次首先要将每次首先要将riri 移到移到r0r0，故每趟移动比比较多，故每趟移动比比较多一次，则记录移动的总次数为：一次，则记录移动的总次数为：2022年8月3日星期三
18、 因此，直接插入排序算法最坏情况下的时间复杂度因此，直接插入排序算法最坏情况下的时间复杂度为为O(nO(n2 2)。(3)(3)平均情况：平均情况下，参加排序的原始记录关平均情况：平均情况下，参加排序的原始记录关键字是随机排列的，则数据元素的期望比较次数和期望键字是随机排列的，则数据元素的期望比较次数和期望移动次数约为移动次数约为n n2 2/4/4。因此，直接插入排序算法的期望时。因此，直接插入排序算法的期望时间复杂度为间复杂度为O(nO(n2 2)。2022年8月3日星期三 可见，原始数据元素集合越接近有序，直接插入可见，原始数据元素集合越接近有序，直接插入排序算法的时间效率越高，其时间效
19、率位排序算法的时间效率越高，其时间效率位O(nO(n)O(nO(n2 2)。直接插入排序所需的辅助空间是一个监视哨，其作用直接插入排序所需的辅助空间是一个监视哨，其作用是暂时存放待插入的元素，故空间复杂度为是暂时存放待插入的元素，故空间复杂度为O(1)O(1)。显然，直接插入排序算法是一种简单的、稳定的、显然，直接插入排序算法是一种简单的、稳定的、易实现的排序算法，但当记录数易实现的排序算法，但当记录数n n很大时，不适合进行很大时，不适合进行直接插入排序。直接插入排序。2022年8月3日星期三 希尔排序（希尔排序（Shells sortShells sort）又称）又称“缩小增量排缩小增量排
20、序序”（diminishing increment sortdiminishing increment sort），），19591959年由希年由希尔（尔（D.L.ShellD.L.Shell）提出的一种排序方法，它在时间效）提出的一种排序方法，它在时间效率上比其他的插入排序方法有了较大的提高。率上比其他的插入排序方法有了较大的提高。它的基本思想是：把待排序的记录分成若干个它的基本思想是：把待排序的记录分成若干个小组，然后对同一组内的记录进行直接插入排序，待小组，然后对同一组内的记录进行直接插入排序，待整个序列中的记录整个序列中的记录“基本有序基本有序”时，再对全体记录进时，再对全体记录进行一
21、次直接插入排序。行一次直接插入排序。8.2.2 8.2.2 希尔排序希尔排序2022年8月3日星期三 希尔排序的过程如下：希尔排序的过程如下：(1)(1)以以d d1 1(0d(0d1 1n-1)dd2 2）为增量，重复上述步骤，直到）为增量，重复上述步骤，直到d di i=1,=1,把把所有所有n n个元素放在一个组内，进行直接插入排序为止。个元素放在一个组内，进行直接插入排序为止。该次排序结束时，这个序列的排序工作完成。该次排序结束时，这个序列的排序工作完成。2022年8月3日星期三 希尔排序实际上是对直接插入排序的一种改进。待希尔排序实际上是对直接插入排序的一种改进。待排序的原始序列越接
22、近有序或者记录个数越少，则直排序的原始序列越接近有序或者记录个数越少，则直接插入排序算法的时间效率就越高。接插入排序算法的时间效率就越高。在希尔排序中，开始增量比较大，分组较多，每在希尔排序中，开始增量比较大，分组较多，每个组内记录个数较少，因而记录的比较次数和移动次个组内记录个数较少，因而记录的比较次数和移动次数都比较少，在小组内用直接插入排序的时间效率很数都比较少，在小组内用直接插入排序的时间效率很高。尽管增量逐渐变小，分组越来越少，每个组内记高。尽管增量逐渐变小，分组越来越少，每个组内记录个数逐渐增多，但同时记录越来越接近有序，因而录个数逐渐增多，但同时记录越来越接近有序，因而记录的比较
23、次数和移动次数越来越少，从而使直接插记录的比较次数和移动次数越来越少，从而使直接插入排序的时间效率越来越高。入排序的时间效率越来越高。2022年8月3日星期三 在希尔排序中，增量序列的选取到目前为止尚未得在希尔排序中，增量序列的选取到目前为止尚未得到一个最佳值，但最后一次排序时的增量必为到一个最佳值，但最后一次排序时的增量必为1 1。一般。一般选取增量序列的规则是：取选取增量序列的规则是：取d di+1i+1为为 ，最简单的方法是取，最简单的方法是取d di+1i+1=【例【例8-28-2】已知一组待排序的记录的初始序列为已知一组待排序的记录的初始序列为36,45,60,92,78,12,25
24、,45,18,2,36,45,60,92,78,12,25,45,18,2,用希尔排序用希尔排序法对其进行排序，并给出排序的过程。法对其进行排序，并给出排序的过程。id/3id/2id/22022年8月3日星期三解：希尔排序的过程如下图所示。在图中，同一连线上解：希尔排序的过程如下图所示。在图中，同一连线上的关键字表明它们所属的记录是放在同一组中的，选取的关键字表明它们所属的记录是放在同一组中的，选取增量序列为：增量序列为：d1=5d1=5，d2=3d2=3，d3=1d3=1，同时用，同时用“”标记后标记后一个一个4545来检测排序的稳定性。来检测排序的稳定性。2022年8月3日星期三 希尔排
25、序算法的具体实现如算法希尔排序算法的具体实现如算法8.28.2所示。所示。void ShellInsert(SqList&L,int d,intvoid ShellInsert(SqList&L,int d,int t)t)/对顺序表对顺序表L L作希尔排序作希尔排序for(k=0;kt;+kfor(k=0;kt;+k)/参数参数t t为希尔排序趟数为希尔排序趟数for(i=dk+1;i=L.length;+ifor(i=dk+1;i=L.length;+i)/一趟增量为一趟增量为dkdk 的插入排序的插入排序 if(L.ri.keyL.ri-dk.keyif(L.ri.key0)&(L.r0
26、.key0)&(L.r0.keyL.r2.key,L.r1.keyL.r2.key,则将两个记录交换。然后比较第则将两个记录交换。然后比较第2 2个和第个和第3 3个记录的关个记录的关键字；以此类推，直到第键字；以此类推，直到第n-1n-1个记录和第个记录和第n n个记录的关个记录的关键字进行比较交换，这个过程称为一趟冒泡。键字进行比较交换，这个过程称为一趟冒泡。(2)(2)然后进行第二趟冒泡排序，即对然后进行第二趟冒泡排序，即对2n2n个记录进行同个记录进行同样操作，则关键字次大的记录被安置在第样操作，则关键字次大的记录被安置在第n-1n-1条记录的条记录的位置上。位置上。(3)(3)重复对
27、前重复对前n-in-i（i1i1）条记录进行相同的操作，每次）条记录进行相同的操作，每次操作都将关键字次大的记录安置到第操作都将关键字次大的记录安置到第n-in-i条记录的位置条记录的位置上，直至没有记录需要交换为止。上，直至没有记录需要交换为止。2022年8月3日星期三 一般地，冒泡排序的第一般地，冒泡排序的第i i趟排序只需要从趟排序只需要从L.r1L.r1到到L.rn-i+1L.rn-i+1条记录依次比较相邻的两个记录的关条记录依次比较相邻的两个记录的关键字，并在出现前一条记录的关键字大于后一条记录键字，并在出现前一条记录的关键字大于后一条记录的关键字的时候进行交换，其结果就是将这的关键
28、字的时候进行交换，其结果就是将这n-i+1n-i+1条条记录中关键字最大的记录移到第记录中关键字最大的记录移到第n-i+1n-i+1条记录的位置条记录的位置上。整个冒泡排序的过程最多需要进行上。整个冒泡排序的过程最多需要进行k(1kn)k(1kn)趟。趟。2022年8月3日星期三 【例【例8-38-3】已知一组待排序的记录的初始序列为已知一组待排序的记录的初始序列为78,45,60,36,25,45,12,9278,45,60,36,25,45,12,92，用冒泡排序法，用冒泡排序法对其进行排序。对其进行排序。解：冒泡排序的过程如下图所示。其中后一个解：冒泡排序的过程如下图所示。其中后一个45
29、45用用“”标记，来检查排序的稳定性。标记，来检查排序的稳定性。2022年8月3日星期三在冒泡排序过程中，关键字较小的记录好比水中在冒泡排序过程中，关键字较小的记录好比水中的气泡逐趟向上浮，关键字较大的记录好比石块往下的气泡逐趟向上浮，关键字较大的记录好比石块往下沉，每一趟中都有一块大沉，每一趟中都有一块大“石块石块”沉到水底，图中用沉到水底，图中用加粗字体标记。加粗字体标记。若在排序过程中，当前的排序序列已经有序，就若在排序过程中，当前的排序序列已经有序，就无须再继续比较，可提前结束排序过程，为此在实际无须再继续比较，可提前结束排序过程，为此在实际的冒泡算法中引入一个整型量的冒泡算法中引入一
30、个整型量flagflag，在每一次排序之，在每一次排序之前，先将它置为前，先将它置为0 0，若在一次排序中交换了记录，则，若在一次排序中交换了记录，则将它置为将它置为1 1。当一次排序结束时，再检查。当一次排序结束时，再检查flagflag，若，若flagflag仍为仍为0 0，则未曾交换过记录，此时可以提前终止，则未曾交换过记录，此时可以提前终止算法。算法。2022年8月3日星期三 冒泡排序算法的具体实现如冒泡排序算法的具体实现如算法算法8.38.3所示。所示。算法分析：算法分析：冒泡排序是一种稳定的排序方法，算法的执行时间冒泡排序是一种稳定的排序方法，算法的执行时间与原始记录的有序程度有很
31、大关系，如果原始记录已经与原始记录的有序程度有很大关系，如果原始记录已经是正序序列，比较次数为是正序序列，比较次数为n-1n-1次，交换次数为次，交换次数为0 0；如果原；如果原始记录是反序排列，则总的比较次数为始记录是反序排列，则总的比较次数为n(n-1)/2n(n-1)/2次，交次，交换次数为换次数为3n(n-1)/23n(n-1)/2。所以算法的平均时间复杂度为。所以算法的平均时间复杂度为O(nO(n2 2)，空间复杂度为，空间复杂度为O(1)O(1)。2022年8月3日星期三 快速快速排序（排序（quick sortquick sort）是对冒泡排序的一种改）是对冒泡排序的一种改进。它
32、的基本思想：通过一趟排序将待排序记录分割进。它的基本思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续部分记录的关键字小，则可分别对这两部分记录继续进行排序，直至整个序列进行排序，直至整个序列有序。有序。8.3.2 8.3.2 快速排序快速排序2022年8月3日星期三 1 1快速排序过程快速排序过程 快速排序在待排序的快速排序在待排序的n n个记录中任取一个记录（如个记录中任取一个记录（如取第一个记录），以该记录的键值为标准，将所有记取第一个记录），以该记录的键值为标准，将
33、所有记录分为两组（一般都是无序的），使得第一组中各记录分为两组（一般都是无序的），使得第一组中各记录的键值均小于或等于该键值，第二组中各记录的键录的键值均小于或等于该键值，第二组中各记录的键值均大于该键值，然后把该记录排在这两组的中间值均大于该键值，然后把该记录排在这两组的中间（这也是该记录最终的位置），称为一趟快速排序（这也是该记录最终的位置），称为一趟快速排序（或一次划分）。对所分成的两组再分别重复上述方（或一次划分）。对所分成的两组再分别重复上述方法，直到所有记录都排在适当位置为止。法，直到所有记录都排在适当位置为止。2022年8月3日星期三 快速快速排序的思想：排序的思想：(1)(1)
34、先将待排序序列的第一个记录先将待排序序列的第一个记录L.r1L.r1复制到复制到L.r0L.r0。(2)(2)确定支点确定支点i i的位置：将的位置：将所有关键字比所有关键字比L.ri.keyL.ri.key小的小的记录安置到记录安置到i i位置之前，将所有关键字比位置之前，将所有关键字比L.ri.keyL.ri.key大大的记录安置到的记录安置到i i位置之后。最后以位置之后。最后以i i位置作为分界线，将位置作为分界线，将序列序列L.r1,L.rnL.r1,L.rn分割成两个子序列分割成两个子序列L.r1,L.r2,L.ri-1L.r1,L.r2,L.ri-1和和L.ri+1,L.ri+2
35、,L.rnL.ri+1,L.ri+2,L.rn。前一个子序列中的。前一个子序列中的记录的关键字都比记录的关键字都比L.ri.keyL.ri.key小，后一个序列中的记录小，后一个序列中的记录关键字都比关键字都比L.ri.keyL.ri.key大。大。(3)(3)将将L.r0L.r0复制到复制到L.riL.ri 中。中。(4)(4)对被分割的两个序列重复进行对被分割的两个序列重复进行(1)(1)和和(2)(2)步骤，直到步骤，直到每个序列的记录数都为每个序列的记录数都为1 1，达到整个序列有序。，达到整个序列有序。2022年8月3日星期三 【例【例8-48-4】已知一组待排序的记录的初始序列为已
36、知一组待排序的记录的初始序列为45,45,45,60,36,25,78,12,9245,60,36,25,78,12,92，用快速排序法对其进，用快速排序法对其进行排序。行排序。解：取初始序列的第一个记录为排序支点，其关键解：取初始序列的第一个记录为排序支点，其关键字记为字记为pivotkeypivotkey，将其复制到，将其复制到L.r0L.r0中。设中。设i i和和j j用于存用于存储序列向后和向前搜索的位置。储序列向后和向前搜索的位置。从从j j位置开始向序列的前部搜索，如果位置开始向序列的前部搜索，如果L.rj.keypivotkeyL.rj.keypivotkeyL.ri.keypi
37、votkey，则用，则用L.riL.ri 和关键字为和关键字为pivotkeypivotkey的记录进行交换，直到的记录进行交换，直到i i和和j j相等完成一趟排序。相等完成一趟排序。在形成的子序列中，分别以子序列的第一个记录为排在形成的子序列中，分别以子序列的第一个记录为排序支点，重复上述步骤，直到两个子序列中的记录数为序支点，重复上述步骤，直到两个子序列中的记录数为1 1，达到整个序列有序。排序过程如达到整个序列有序。排序过程如下下图所示。图所示。2022年8月3日星期三 2 2快速排序的一趟排序算法快速排序的一趟排序算法 快速排序是通过递归的方法实现的，在一趟快速快速排序是通过递归的方
38、法实现的，在一趟快速排序算法中，附设两个整型变量排序算法中，附设两个整型变量lowlow和和highhigh，其初值，其初值分别为第一趟排序序列的上下限，设支点记录的关键分别为第一趟排序序列的上下限，设支点记录的关键字为字为pivotkeypivotkey，则首先从，则首先从highhigh位置起向前搜索找到第位置起向前搜索找到第一个关键字小于一个关键字小于pivotkeypivotkey的记录和支点记录进行交换，的记录和支点记录进行交换，然后从然后从lowlow位置起向后搜索，找到第一个关键字大于位置起向后搜索，找到第一个关键字大于pivotkeypivotkey的记录和支点记录进行交换，重
39、复上述两个的记录和支点记录进行交换，重复上述两个步骤直到步骤直到low=highlow=high为止。为止。快速排序的一趟排序具体实现如快速排序的一趟排序具体实现如算法算法8.48.4所示。所示。2022年8月3日星期三 3.3.快速快速排序的递归算法排序的递归算法 快速排序算法需要对两个子序列分别使用快速排序。快速排序算法需要对两个子序列分别使用快速排序。递归形式的快速排序算法如算法递归形式的快速排序算法如算法8.58.5和算法和算法8.68.6所示。所示。2022年8月3日星期三void QSort(SqList&L,int low,intvoid QSort(SqList&L,int l
40、ow,int high)high)对顺序表的子序列对顺序表的子序列L.rlow.highL.rlow.high 进行快速排序进行快速排序int pivotlocint pivotloc;if(lowif(lowhigh)high)子序列的长度应该大于子序列的长度应该大于1 1 pivotloc=Partition(L,low,high pivotloc=Partition(L,low,high););将序列将序列L.rL.rlow.highlow.high分成两个子序列，返回支点位置分成两个子序列，返回支点位置 QSort(L,low,pivotloc-1);QSort(L,low,pivot
41、loc-1);对低端子序列进行递归的快速排序对低端子序列进行递归的快速排序 QSort(L,pivotloc+1,high);QSort(L,pivotloc+1,high);对高端子序列进行递归的快速排序对高端子序列进行递归的快速排序 QSort QSort算法算法8.58.52022年8月3日星期三void QuickSort(SqListvoid QuickSort(SqList&L)&L)对顺序表对顺序表L L作快速排序作快速排序QSort(L,1,L.length);QSort(L,1,L.length);QuickSortQuickSort算法算法8.68.6 算法分析：算法分析：
42、快速排序并没有每次比较都进行交换，只是移动快速排序并没有每次比较都进行交换，只是移动一个数据，待所选出的元素找到合适的位置才存入，一个数据，待所选出的元素找到合适的位置才存入，因此排序速度快。因此排序速度快。2022年8月3日星期三 快速排序的执行时间和排序支点的选取有关，若快速排序的执行时间和排序支点的选取有关，若支点的关键字能把当前记录从中间分成两个相等的子支点的关键字能把当前记录从中间分成两个相等的子区间，则运行效率最高；若记录有序，且支点的关键区间，则运行效率最高；若记录有序，且支点的关键字在记录的首或尾时，即只有一个子区间，该算法就字在记录的首或尾时，即只有一个子区间，该算法就退化成
43、冒泡排序法，此种情况为最坏的情况，其算法退化成冒泡排序法，此种情况为最坏的情况，其算法的时间复杂度为的时间复杂度为O(nO(n2 2)。快速排序的平均时间复杂度快速排序的平均时间复杂度为为O(nlogO(nlog2 2n)n)，它是一种不稳定的排序方法。，它是一种不稳定的排序方法。2022年8月3日星期三8.48.4 选择排序选择排序 选择排序（选择排序（selection sortselection sort）就是每一趟从待排）就是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数序放在已排好
44、序的数列的最后，直到全部待排序的数据元素排完。选择排序中最简单的就是简单选择排序据元素排完。选择排序中最简单的就是简单选择排序（simple selection sortsimple selection sort）。）。2022年8月3日星期三 算法思想：算法思想：对于表对于表L L中的中的n n条记录进行简单选择排序，对于第条记录进行简单选择排序，对于第i i趟选择就是从趟选择就是从n-i+1n-i+1（i=1,2,n-1i=1,2,n-1）个记录中选取）个记录中选取关键字最小的记录作为有序序列中的第关键字最小的记录作为有序序列中的第i i个记录。个记录。【例【例8-58-5】已知一组待排序
45、的记录的初始序列为已知一组待排序的记录的初始序列为45,45,60,36,25,78,12,9245,45,60,36,25,78,12,92，用简单选择排，用简单选择排序法对其排序。序法对其排序。8.4.1 8.4.1 简单选择排序简单选择排序2022年8月3日星期三 解：第一趟，从待排序的序列中，选择关键字最解：第一趟，从待排序的序列中，选择关键字最小的一个记录与第一个记录进行交换。第二趟，从其小的一个记录与第一个记录进行交换。第二趟，从其余的序列中选择关键字次小的记录与第二个记录进行余的序列中选择关键字次小的记录与第二个记录进行交换，以此类推，直到所有记录排序完成。排序过程交换，以此类推
46、，直到所有记录排序完成。排序过程如下图所示。如下图所示。2022年8月3日星期三 简单选择排序的算法实现如算法简单选择排序的算法实现如算法8.78.7所示。所示。void SelectSort(SqListvoid SelectSort(SqList&L)&L)/对顺序表对顺序表L L进行简单选择排序进行简单选择排序for(ifor(i=0;iL.length-1;i+)=0;iL.length-1;i+)/选择第选择第i+1i+1小的记录，并和第小的记录，并和第i+1i+1位置的记录交换位置的记录交换k=i;k=i;for(jfor(j=i+1;j=L.length-1;j+)=i+1;jL
47、.rj.keyif(L.rk.keyL.rj.key)k=j;k=j;if(k if(k!=i)!=i)/将第将第i+1i+1个记录与第个记录与第k+1k+1个记录交换个记录交换 t=L.ri;L.ri=L.rk;L.rkt=L.ri;L.ri=L.rk;L.rk=t;=t;/SelectSort/SelectSort算法算法8.78.72022年8月3日星期三 算法分析：算法分析：在简单选择排序中，记录的比较次数与记录关键在简单选择排序中，记录的比较次数与记录关键字的初始状态无关，无论关键字的初始状态如何，每字的初始状态无关，无论关键字的初始状态如何，每趟选择排序都要进行趟选择排序都要进行n
48、-in-i次比较，才能找出关键字最小次比较，才能找出关键字最小的记录。但记录的移动次数与记录关键字的初始状态的记录。但记录的移动次数与记录关键字的初始状态有关。在最好情况下，其初始记录关键字为正序，每有关。在最好情况下，其初始记录关键字为正序，每趟排序不用交换记录，记录移动次数为趟排序不用交换记录，记录移动次数为0 0次；平均情况次；平均情况下，记录移动的次数会比较高。所以简单选择排序在下，记录移动的次数会比较高。所以简单选择排序在最好情况和平均情况下，总的时间复杂度均为最好情况和平均情况下，总的时间复杂度均为O(nO(n2 2)，这是由它的比较次数决定的。简单选择排序只需要一这是由它的比较次
49、数决定的。简单选择排序只需要一个临时单元交换记录，因此，简单选择排序的空间复个临时单元交换记录，因此，简单选择排序的空间复杂度为杂度为O(1)O(1)。2022年8月3日星期三8.4 8.4 选择排序选择排序 在简单选择排序中，待排序的序列构成一个线性表结构，在简单选择排序中，待排序的序列构成一个线性表结构，要从有要从有n n个数据元素的线性表中选择出一个最小的数据元素个数据元素的线性表中选择出一个最小的数据元素需要比较需要比较n-1n-1次。堆排序（次。堆排序（heap sortheap sort）是对选择排序的一）是对选择排序的一种改进方法，属于树型排序法。在排序过程中，将种改进方法，属于
50、树型排序法。在排序过程中，将R1.nR1.n看成是一棵完全二叉树的顺序存储结构，利用双亲结点和孩看成是一棵完全二叉树的顺序存储结构，利用双亲结点和孩子结点间的内在关系来选择关键字最小的记录。子结点间的内在关系来选择关键字最小的记录。8.4.2 8.4.2 堆排序堆排序2022年8月3日星期三 1.1.堆的概念堆的概念 设有设有n n个元素的序列个元素的序列K1,K2,KnK1,K2,Kn，当且仅当满，当且仅当满足下述关系之一时，称之为堆。足下述关系之一时，称之为堆。（其中，（其中，i=1,2,i=1,2,）n22022年8月3日星期三 堆的含义表明，完全二叉树中所有非终端结点的值堆的含义表明，
