数据结构与算法数据结构与算法 (10).ppt

《数据结构与算法数据结构与算法 (10).ppt》由会员分享，可在线阅读，更多相关《数据结构与算法数据结构与算法 (10).ppt（135页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法与数据结构算法与数据结构2 2第第四四部分部分 集合结构集合结构n集合中的元素互相之间没有关系集合中的元素互相之间没有关系n集合的存储：借用其他容器集合的存储：借用其他容器n集合的操作：查找和排序集合的操作：查找和排序n这一部分将介绍这一部分将介绍n查找表查找表(静态查找表、动态查找表静态查找表、动态查找表)n散列表散列表n排序算法排序算法3 3第第 12 12 章章 排序排序n12.1 12.1 排序的基本概念排序的基本概念n12.2 12.2 插入排序插入排序n12.3 12.3 交换排序交换排序n12.4 12.4 选择排序选择排序n12.5 12.5 归并排序归并排序n*12.6

2、12.6 基数排序基数排序n12.712.7 各种内部排序方法的比较各种内部排序方法的比较n*12.8 12.8 外部排序外部排序n*内容可不讲内容可不讲4 4排序问题排序问题nGoogleGoogle等搜索引擎返回结果排级等搜索引擎返回结果排级n图书馆员书目编号、上架图书馆员书目编号、上架n各种排名各种排名n大学排名大学排名n考试成绩排名考试成绩排名n福布斯福布斯 富豪榜富豪榜nWindowsWindows资源管理器，文件查看资源管理器，文件查看n5 5n所谓排序就是把集合中的数据元素按照它们的关键所谓排序就是把集合中的数据元素按照它们的关键字的非递减或非递增序排成一个序列。字的非递减或非递

3、增序排成一个序列。n内排序与外排序：内排序与外排序：n内排序是指被排序的数据元素全部存放在计算机的内存内排序是指被排序的数据元素全部存放在计算机的内存之中，并且在内存中调整数据元素的相对位置。之中，并且在内存中调整数据元素的相对位置。n外排序是指在排序的过程中，数据元素主要存放在外存外排序是指在排序的过程中，数据元素主要存放在外存储器中，借助于内存储器逐步调整数据元素之间的相对储器中，借助于内存储器逐步调整数据元素之间的相对位置。位置。排序的基本概念排序的基本概念6 6n稳定排序稳定排序n存在多个具有相同排序码的记录存在多个具有相同排序码的记录n排序后这些记录的相对次序保持不变排序后这些记录的

4、相对次序保持不变 n稳定性例稳定性例1 1n 3434 12 12 3434 08 96 08 96n 08 12 08 12 3434 3434 96 96 稳定！定！排序的基本概念排序的基本概念7 7n稳定性稳定性n存在多个具有相同排序码的记录存在多个具有相同排序码的记录n排序后这些记录的相对次序保持不变排序后这些记录的相对次序保持不变 n稳定性例稳定性例2 2n 3434 12 12 3434 08 96 08 96n 08 12 08 12 3434 34 34 96 96 不不稳定！定！排序的基本概念排序的基本概念8 8排序排序算法算法的衡量标准的衡量标准n时间代价时间代价记录的比较

5、和移动次数记录的比较和移动次数 n空间代价空间代价n算法本身的繁杂程度算法本身的繁杂程度 9 9第第 12 12 章章 排序排序n12.1 12.1 排序的基本概念排序的基本概念n12.2 12.2 插入排序插入排序n12.2.1 12.2.1 直接插入排序直接插入排序n12.2.2 12.2.2 折半插入排序折半插入排序n12.2.3 12.2.3 希尔排序希尔排序n12.3 12.3 交换排序交换排序n12.4 12.4 选择排序选择排序n12.5 12.5 归并排序归并排序n*12.6 12.6 基数排序基数排序n12.712.7 各种内部排序方法的比较各种内部排序方法的比较n*12.8

6、 12.8 外部排序外部排序1010直接直接插入排序插入排序n直接直接插入排序插入排序（Straight Insertion SortStraight Insertion Sort）：假设）：假设在在排序过程中，记录序列为排序过程中，记录序列为R0.n-1R0.n-1，首先将第一个记，首先将第一个记录录R0R0看做一个有序子序列，然后依次将记录看做一个有序子序列，然后依次将记录RiRi（1in-11in-1）插入到有序子序列）插入到有序子序列R0.i-1R0.i-1中，中，使记录的有序子序列从使记录的有序子序列从R0.i-1R0.i-1变为变为R0.iR0.i。1111直接直接插入排序插入排序

7、算法与数据结构1212直接插入排序直接插入排序1234322964453478 发现逆序逆序对，交，交换吗？1313n 代码代码12.112.1template template void straightInsertSort(Type R,int size)void straightInsertSort(Type R,int size)int pos,j;int pos,j;/pospos为待插入记录位置为待插入记录位置 Type tmp;Type tmp;for(pos=1;pos size;pos+)for(pos=1;pos size;pos+)tmp=Rpos;tmp=Rpos;/将

8、待插入记录放进临时将待插入记录放进临时变量变量 /从后向前查找插入从后向前查找插入位置位置 for(j=pos-1;tmp=0;j-)for(j=pos-1;tmp=0;j-)Rj+1 Rj+1=Rj;=Rj;/将大于待插入记录的记录向后移动将大于待插入记录的记录向后移动 Rj+1=tmp;Rj+1=tmp;/将待插入记录放到合适位置将待插入记录放到合适位置 算法与数据结构直接直接插入排序插入排序1414算法分析算法分析n稳定稳定n空间代价：空间代价：O(1)O(1)n时间代价：时间代价：n最佳情况：最佳情况：n-1n-1次比较，次比较，2(n-1)2(n-1)次移动，次移动，(n)(n)n最

9、差情况：最差情况：O(nO(n2 2)比较次数比较次数为为移动移动次数为次数为n平均情况：平均情况：O(nO(n2 2)n适用情况：排序元数较少，且几乎是已排序的适用情况：排序元数较少，且几乎是已排序的15152023/3/302023/3/301515直接插入排序的优缺点直接插入排序的优缺点n直接直接插入排序算法简单插入排序算法简单,当待排序记录数量当待排序记录数量n n很很小时小时,局部有序时局部有序时,较为适用较为适用。当。当n n很大时很大时,其效其效率不高率不高。n若若对直接插入排序算法进行改进对直接插入排序算法进行改进,可从减少可从减少“比比较较”和和“移动移动”次数这两方面着手次

10、数这两方面着手。n折半折半存入排序、二路插入排序、表插入排序、存入排序、二路插入排序、表插入排序、希尔排序都是对直接插入排序的改进希尔排序都是对直接插入排序的改进。1616第第 12 12 章章 排序排序n12.1 12.1 排序的基本概念排序的基本概念n12.2 12.2 插入排序插入排序n12.2.1 12.2.1 直接插入排序直接插入排序n12.2.2 12.2.2 折半插入排序折半插入排序n12.2.3 12.2.3 希尔排序希尔排序n12.3 12.3 交换排序交换排序n12.4 12.4 选择排序选择排序n12.5 12.5 归并排序归并排序n*12.6 12.6 基数排序基数排序

11、n12.712.7 各种内部排序方法的比较各种内部排序方法的比较n*12.8 12.8 外部排序外部排序1717 折半插入排序折半插入排序n折半插入排序折半插入排序（Binary Insertion SortBinary Insertion Sort）：当）：当第第i i个记录个记录要插入前要插入前i i1 1个有序记录序列时，可利用折半查找（在查个有序记录序列时，可利用折半查找（在查找章节已介绍）方式确定插入位置，以减少比较次数。找章节已介绍）方式确定插入位置，以减少比较次数。从从而达到减少比较次数的目的而达到减少比较次数的目的 n 代码代码12.212.2template template

12、 void binaryInsertSort(Type R,int size)void binaryInsertSort(Type R,int size)int pos,j,low,high,mid;int pos,j,low,high,mid;Type tmp;Type tmp;1818 for(pos=1;possize;pos for(pos=1;possize;pos+)/+)/假定第一个记录有序假定第一个记录有序 tmp tmp=Rpos;=Rpos;/将待排记录将待排记录RposRpos暂存到暂存到tmptmp low low=0;high=pos-1=0;high=pos-1;/

13、;/设置折半查找的范围设置折半查找的范围 while(low=high)while(low=high)/折半查找插入折半查找插入位置位置 mid=(low+high)/2;mid=(low+high)/2;/计算中间位置计算中间位置 if(tmp Rmid)high=mid-1;if(tmp=low;j-)for(j=pos-1;j=low;j-)Rj+1=Rj;Rj+1=Rj;/记录后移记录后移 Rlow=tmp;Rlow=tmp;/插入待排序记录插入待排序记录 折半插入排序折半插入排序1919n折半插入排序比直接插入排序明显地减少了关键字间的折半插入排序比直接插入排序明显地减少了关键字间的

14、“比较比较”次数，但记录次数，但记录“移动移动”的次数不变，故其时间复杂的次数不变，故其时间复杂度仍为度仍为O O（n n2 2）。）。算法与数据结构算法分析算法分析2020自测题自测题1 1对同一待排序列分别进行折半插入排序和直接插入排对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（序，两者之间可能的不同之处是（）。）。A A排序的总趟数排序的总趟数B B元素的移动次数元素的移动次数C C使用辅助空间的数量使用辅助空间的数量D D元素之间的比较次数元素之间的比较次数【20122012年全国硕士研究生入学统一考试计算机学科专业基础综合】年全国硕士研究生入学统一考试计

15、算机学科专业基础综合】【参考答案】【参考答案】D D算法与数据结构2121第第 12 12 章章 排序排序n12.1 12.1 排序的基本概念排序的基本概念n12.2 12.2 插入排序插入排序n12.2.1 12.2.1 直接插入排序直接插入排序n12.2.2 12.2.2 折半插入排序折半插入排序n12.2.3 12.2.3 希尔排序希尔排序n12.3 12.3 交换排序交换排序n12.4 12.4 选择排序选择排序n12.5 12.5 归并排序归并排序n*12.6 12.6 基数排序基数排序n12.712.7 各种内部排序方法的比较各种内部排序方法的比较n*12.8 12.8 外部排序外

16、部排序2222希尔排序希尔排序n希尔排序希尔排序（Shell SortShell Sort）又称为缩小增量排序，是由）又称为缩小增量排序，是由D.L.ShellD.L.Shell在在19591959年提出的。年提出的。ShellShell从从“减少记录个数减少记录个数”和和“基本有序基本有序”两方面对直接插入排序进行了改进。两方面对直接插入排序进行了改进。n希尔排序的基本思想是：将待排序的记录划分成几组，希尔排序的基本思想是：将待排序的记录划分成几组，间距相同的记录分在一组，对各组分别实施直接插入间距相同的记录分在一组，对各组分别实施直接插入排序。当经过几次分组排序后，记录的排列已经基本排序。

17、当经过几次分组排序后，记录的排列已经基本有序，再对所有的记录实施最后的直接插入排序。有序，再对所有的记录实施最后的直接插入排序。n通过分组，一方面减少了参与直接插入排序的数据量；通过分组，一方面减少了参与直接插入排序的数据量；另一方面先比较那些间距较大的记录，避免频繁的移另一方面先比较那些间距较大的记录，避免频繁的移动相邻记录。当待排序记录个数较少且待排序记录已动相邻记录。当待排序记录个数较少且待排序记录已基本有序时，直接插入排序的效率是较高的。基本有序时，直接插入排序的效率是较高的。2323希尔排序算法思想希尔排序算法思想n对于有对于有n n个记录的初始序列，希尔排序的具体步骤如下：个记录的

18、初始序列，希尔排序的具体步骤如下：n(1)(1)首先取一个整数首先取一个整数gapngapn作为增量；作为增量；n(2)(2)将全部记录分为将全部记录分为gapgap个子序列，所有间距为个子序列，所有间距为gapgap的的记录分在同一个子序列中，对每个子序列分别实施直记录分在同一个子序列中，对每个子序列分别实施直接插入排序；接插入排序；n(3)(3)然后缩小增量然后缩小增量gapgap，重复步骤，重复步骤(2)(2)的子序列划分和的子序列划分和排序工作，直到最后排序工作，直到最后gapgap等于等于1 1，将所有记录放在一组，将所有记录放在一组，进行最后一次直接插入排序。进行最后一次直接插入排

19、序。2424GapGap的选取的选取算法与数据结构2525希尔排序希尔排序算法与数据结构2626希希尔排序的实现尔排序的实现 n若以若以ShellShell提出的分组方法，则提出的分组方法，则ShellShell排序的算法排序的算法如下如下n 代码代码12.312.3template template void shellSort(Type R,int size)void shellSort(Type R,int size)int gap,pos,j;int gap,pos,j;/gap/gap为希尔为希尔增量增量，pospos为待插入记录为待插入记录位置位置 Type tmp;Type tm

20、p;for(gap=size/2;gap 0;gap/=2 for(gap=size/2;gap 0;gap/=2)for(pos=gap;pos size;pos+)for(pos=gap;pos=0&Rj tmp;j-=gap)for(j=pos-gap;j=0&Rj tmp;j-=gap)Rj+gap=Rj;Rj+gap=Rj;/记录后移记录后移 Rj+gap=tmp;Rj+gap=tmp;/将待插入记录放到合适位置将待插入记录放到合适位置 2727性能分析性能分析n不同的增量序列有不同的时间性能。不同的增量序列有不同的时间性能。n希尔排序适用于待排序的记录数目较大的情况。希尔排序适用于

21、待排序的记录数目较大的情况。n希希尔尔排序存在大跨度的元素移动，是排序存在大跨度的元素移动，是一种不稳定的排序方法一种不稳定的排序方法。n希希尔排序的时间性能与其选定的增量序列有关，有人在大量尔排序的时间性能与其选定的增量序列有关，有人在大量实验的基础上推导出，希尔排序的时间复杂度约为实验的基础上推导出，希尔排序的时间复杂度约为O O（n n1.31.3）。n空间空间复杂度为复杂度为O(1)O(1)。2828自测题自测题2 2用希尔排序方法对一个数据序列进行排序时，若第用希尔排序方法对一个数据序列进行排序时，若第1 1趟排趟排序结果为序结果为9 9，1 1，4 4，1313，7 7，8 8，2

22、020，2323，1515，则该趟排序采，则该趟排序采用的增量（间隔）可能是（用的增量（间隔）可能是（）。）。A A2 2B B3 3C C4 4D D5 5【20122012年全国硕士研究生入学统一考试计算机学科专业基础综合】年全国硕士研究生入学统一考试计算机学科专业基础综合】【参考答案】【参考答案】B B算法与数据结构2929自测题自测题3 3希尔排序的组内排序采用的是（希尔排序的组内排序采用的是（）。）。A A直接插入排序直接插入排序 B B折半插入排序折半插入排序C C快速排序快速排序 D D归并排序归并排序【20152015年全国硕士研究生入学统一考试计算机学科专业基础综合】年全国硕

23、士研究生入学统一考试计算机学科专业基础综合】【参考答案】【参考答案】A A算法与数据结构30302023/3/302023/3/303030*自测题：希尔排序自测题：希尔排序二趟排序二趟排序结果：果：17 10 51 33 28 51 52 62 96 87三趟排序三趟排序结果：果：10 17 28 33 51 51 52 62 87 96初始关初始关键字序列：字序列：51 33 62 96 87 17 28 51 52 10一趟排序一趟排序结果：果：17 28 51 52 10 51 33 62 96 8731312023/3/302023/3/303131*自测题自测题请给出对一组记录请给

24、出对一组记录（54,38,96,23,15,90,72,60,45,8354,38,96,23,15,90,72,60,45,83）进行希尔排序（增量序列为进行希尔排序（增量序列为5,3,15,3,1）时的排序过程。）时的排序过程。3232第第 12 12 章章 排序排序n12.1 12.1 排序的基本概念排序的基本概念n12.2 12.2 插入排序插入排序n12.3 12.3 交换排序交换排序n12.3.1 12.3.1 冒泡排序冒泡排序n12.3.2 12.3.2 快速排序快速排序n12.4 12.4 选择排序选择排序n12.5 12.5 归并排序归并排序n*12.6 12.6 基数排序基

25、数排序n12.712.7 各种内部排序方法的比较各种内部排序方法的比较n*12.8 12.8 外部排序外部排序3333冒泡排序冒泡排序n冒泡排序冒泡排序(Bubble Sort(Bubble Sort，也称为起泡排序，也称为起泡排序)是一种比较简是一种比较简单的交换排序方法。它的基本思想是对所有相邻记录的关单的交换排序方法。它的基本思想是对所有相邻记录的关键字值进行比较，如果不满足排序要求（即逆序），则将键字值进行比较，如果不满足排序要求（即逆序），则将其交换，最终直到所有记录排好序为止其交换，最终直到所有记录排好序为止。3434冒泡排序冒泡排序n对于由对于由n n个记录序列个记录序列的非递减

26、序的非递减序冒泡排序冒泡排序的步骤如下：的步骤如下：n(1)(1)将整个待排序的记录序列划分成有序区和无序区，将整个待排序的记录序列划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录；初始状态有序区为空，无序区包括所有待排序的记录；n(2)(2)每一趟冒泡排序，对无序区从头到尾比较相邻记每一趟冒泡排序，对无序区从头到尾比较相邻记录的关键字，若逆序，录的关键字，若逆序，则则交换交换。一趟排序后无序区中一趟排序后无序区中关键字值最大的记录进入到有序区；关键字值最大的记录进入到有序区；n(3)(3)重复执行步骤重复执行步骤(2)(2)，若在某一趟排序中没有发生交，若在某一趟排序中没

27、有发生交换操作，说明待排序记录已全部有序，排序提前结束。换操作，说明待排序记录已全部有序，排序提前结束。否则，最多需要经过否则，最多需要经过n n1 1趟冒泡排序，才能将这趟冒泡排序，才能将这n n个记个记录重新按关键字排好序。录重新按关键字排好序。算法与数据结构3535算法与数据结构冒泡排序冒泡排序3636冒泡排序的实现冒泡排序的实现 n冒泡排序算法如下。冒泡排序算法如下。n 代码代码12.412.4template template void bubbleSort(Type R,int size)void bubbleSort(Type R,int size)int i,j;int i,j

28、;bool flag=true;bool flag=true;/记录一趟排序后是否发生过交换记录一趟排序后是否发生过交换 for(i=1;i size&flag;+i)for(i=1;i size&flag;+i)flag=false;flag=false;/假定本趟排序没有交换假定本趟排序没有交换 for(j=0;j size-i;+j)for(j=0;j size-i;+j)if(Rj+1 Rj)if(Rj+1 Rj)/逆序逆序 swap(Rj,Rj+1);swap(Rj,Rj+1);/调用调用STLSTL中的中的swapswap进行交换进行交换 flag=true;flag=true;3

29、737性能分析性能分析n稳定稳定n空间代价：空间代价：O(1)O(1)n时间代价分析：时间代价分析：n比较次数比较次数 ：最少：最少：O(n)O(n)最多：最多：n交换次数最多为交换次数最多为O(nO(n2 2)，最少为，最少为0 0，平均为，平均为O(nO(n2 2)。n时间代价结论时间代价结论n最大，平均时间代价均为最大，平均时间代价均为O(nO(n2 2)。n最小时间代价为最小时间代价为O(n)O(n)：最佳情况下只运行第一轮循环：最佳情况下只运行第一轮循环3838第第 12 12 章章 排序排序n12.1 12.1 排序的基本概念排序的基本概念n12.2 12.2 插入排序插入排序n1

30、2.3 12.3 交换排序交换排序n12.3.1 12.3.1 冒泡排序冒泡排序n12.3.2 12.3.2 快速排序快速排序n12.4 12.4 选择排序选择排序n12.5 12.5 归并排序归并排序n*12.6 12.6 基数排序基数排序n12.712.7 各种内部排序方法的比较各种内部排序方法的比较n*12.8 12.8 外部排序外部排序3939快速排序快速排序n快速排序快速排序(Quick Sort)(Quick Sort)20世世纪十大算法十大算法nTopTenAlgorithmsoftheCenturyn1962London的的ElliotBrothersLtd的的TonyHoar

31、e提提出出的快速排序的快速排序n快速排序也称分区交换排序快速排序也称分区交换排序，是对冒泡排序的改进是对冒泡排序的改进。n在冒泡排序中，记录的比较和移动是在相邻的位置进行在冒泡排序中，记录的比较和移动是在相邻的位置进行的，记录每次交换只能消除一个逆序，因而总的比较和的，记录每次交换只能消除一个逆序，因而总的比较和移动次数较多。移动次数较多。n在在快速排序中，通过分区间的一次交换能消除多个逆序。快速排序中，通过分区间的一次交换能消除多个逆序。实际上，快速排序名副其实，它是目前最快的内部排序实际上，快速排序名副其实，它是目前最快的内部排序算法，被评为算法，被评为“2020世纪十大算法世纪十大算法”

32、。4040快速排序快速排序n算法思想：算法思想：n选择轴值（pivot）n将序列划分将序列划分为两个子序列两个子序列L和和R，使得，使得L中所有中所有记录都小于或等于都小于或等于轴值，R中中记录都大于都大于轴值，轴值处处于于子序列子序列L L和和R R之间，刚好在最终位置。之间，刚好在最终位置。n对子序列子序列L和和R递归进行快速行快速排序，直到子序列只排序，直到子序列只有一个有一个记录为止。止。n基于分治法的排序：快速、基于分治法的排序：快速、归并并4141选择选择轴值n待排序序列的第一个元素作为轴值待排序序列的第一个元素作为轴值n对于随机序列，这个选择是可接受的。对于随机序列，这个选择是可

33、接受的。n对于有序序列，对于有序序列，这样的轴值提供一个糟糕的划分，所有这样的轴值提供一个糟糕的划分，所有的待排序数据都在轴值的一边。因此，这种选择在最坏的待排序数据都在轴值的一边。因此，这种选择在最坏情况下的时间复杂度是平方级的。情况下的时间复杂度是平方级的。n随机选择一个轴值随机选择一个轴值n这样很少有可能选到最差的元素。但随机数的选择也要这样很少有可能选到最差的元素。但随机数的选择也要花相当多的时间。花相当多的时间。n取取N N个数的个数的中值作为轴值中值作为轴值n对轴值的最好选择显然是这个中值，因为它保证对元素对轴值的最好选择显然是这个中值，因为它保证对元素的均匀划分。中值可以通过采样

34、来得到。的均匀划分。中值可以通过采样来得到。4242如何划分如何划分nlowlow、highhigh分别用来分别用来指示左侧指示左侧记录和右侧记录和右侧记录记录n从从右向左开始检查。如果右向左开始检查。如果highhigh的值大于轴的值大于轴tmptmp，该位置中的，该位置中的值位置正确，值位置正确，highhigh减减1 1，继续往前检查，直到遇到一个小于，继续往前检查，直到遇到一个小于k k的值。的值。n将小于将小于k k的这个值放入的这个值放入lowlow的位置。此时的位置。此时highhigh的位置又空出来的位置又空出来了。然后从了。然后从lowlow位置开始从左向右检查，直到遇到一个

35、大于位置开始从左向右检查，直到遇到一个大于轴轴tmptmp的值。的值。n将将lowlow位置的值放入位置的值放入highhigh位置，重复第一步，直到位置，重复第一步，直到lowlow和和highhigh重叠。将轴重叠。将轴tmptmp放入此位置。放入此位置。4343一趟快速排序一趟快速排序n例如，关键字序列例如，关键字序列S=36S=36，8080，4545，6666，2222，9 9，1616，3636。一趟快速。一趟快速排序的过程如下，首先，选取最左侧的排序的过程如下，首先，选取最左侧的3636作枢轴，暂存于临时变量作枢轴，暂存于临时变量tmptmp中，相当于中，相当于lowlow指向空

36、单元指向空单元。n(1)high(1)high从右向左扫描，遇到比从右向左扫描，遇到比3636小的关键字小的关键字1616停止，置停止，置Slow=Slow=ShighShigh 。算法与数据结构4444n(2)low(2)low从左向右扫描，遇到比从左向右扫描，遇到比3636大的关键字大的关键字8080停止，置停止，置Shigh=SlowShigh=Slow 。n(3)high(3)high从右向左扫描，遇到比从右向左扫描，遇到比3636小的关键字小的关键字9 9停止，置停止，置Slow=ShighSlow=Shigh 。算法与数据结构一趟快速排序一趟快速排序4545n(4)low(4)lo

37、w从左向右扫描，遇到比从左向右扫描，遇到比3636大的关键字大的关键字4545停止，置停止，置Shigh=SlowShigh=Slow 。n(5)high(5)high从右向左扫描，遇到比从右向左扫描，遇到比3636小的关键字小的关键字2222停止，置停止，置Slow=Shigh Slow=Shigh。算法与数据结构一趟快速排序一趟快速排序4646n(6)low(6)low从左向右扫描，遇到比从左向右扫描，遇到比3636大的关键字大的关键字6666停止，置停止，置Shigh=SlowShigh=Slow 。n(7)high(7)high从右向左扫描遇到从右向左扫描遇到lowlow，结束一次划分

38、，结束一次划分，low=highlow=high的位置就是轴值的位置就是轴值3636的最终位置，置的最终位置，置Slow=tmpSlow=tmp。3636左侧左侧的关键字均小于它，的关键字均小于它，3636右侧的关键字均大于等于它。右侧的关键字均大于等于它。算法与数据结构一趟快速排序一趟快速排序4747递归快速排序递归快速排序n如果有一个能够完成划分的函数如果有一个能够完成划分的函数partitionpartition，快速排序的，快速排序的实现将非常简单。快速排序是用递归的方式实现的，它的实现将非常简单。快速排序是用递归的方式实现的，它的递归参数就是排序的范围递归参数就是排序的范围 n 代码

39、代码12.612.6递归快速排序。参数为待排序序列递归快速排序。参数为待排序序列S S，以及排，以及排序区间的下界序区间的下界lowlow和上界和上界highhigh。template template void quickSort(Type S,int low,int high)void quickSort(Type S,int low,int high)int pivot;int pivot;if(low=high)return;if(low=high)return;pivot=partition(S,low,high);pivot=partition(S,low,high);/一次划分，

40、返回枢轴位置一次划分，返回枢轴位置 quickSort(S,low,pivot-1);quickSort(S,low,pivot-1);/对枢轴左边一半快速排序对枢轴左边一半快速排序 quickSort(S,pivot+1,high);quickSort(S,pivot+1,high);/对枢轴右边一半快速排序对枢轴右边一半快速排序 4848n 代码代码12.512.5一趟快速排序（或一次划分）。参数为待排序序列一趟快速排序（或一次划分）。参数为待排序序列S S，以及排序，以及排序区间的下界区间的下界lowlow和上界和上界highhigh。template template int part

41、ition(Type S,int low,int high)int partition(Type S,int low,int high)Type tmp=Slow;Type tmp=Slow;/暂存轴值暂存轴值 while(low!=high)while(low!=high)/开始进行分割开始进行分割 while(low=tmp)high-;while(low=tmp)high-;/找找 轴轴值的记录值的记录 if(low high)Slow=Shigh;low+;if(low high)Slow=Shigh;low+;/该记录移动到小下标端该记录移动到小下标端 while(low high&

42、Slow=tmp)low+;while(low high&Slow 轴轴值的记录值的记录 if(low high)Shigh=Slow;high-;if(low high)Shigh=Slow;high-;/该记录移动到大下标端该记录移动到大下标端 Slow=tmp;Slow=tmp;/把轴值回填到分界位置上把轴值回填到分界位置上 return low;return low;/返回枢轴位置返回枢轴位置 一次划分一次划分4949快速排序的快速排序的接口函数接口函数n快速排序的函数原型和其它的排序算法的函数原型都不同，快速排序的函数原型和其它的排序算法的函数原型都不同，它包含了两个用于控制递归终止

43、的参数。为了和其它的排序它包含了两个用于控制递归终止的参数。为了和其它的排序算法一致起来，我们在它外面再加一个算法一致起来，我们在它外面再加一个接口函数接口函数，该函数调，该函数调用了递归的用了递归的quickSortquickSort函数。函数。n 代码代码12.712.7快速排序的接口函数。参数为待排序序列快速排序的接口函数。参数为待排序序列S S，以，以及序列大小及序列大小sizesize。template template void quickSort(Type S,int size)void quickSort(Type S,int size)quickSort(S,0,size-1

44、);quickSort(S,0,size-1);50502023/3/302023/3/305050性能分析性能分析n平均时间复杂度为平均时间复杂度为O O（nlognlog2 2n n）n最差最差时间复杂度时间复杂度为为O(nO(n2 2)n就就平均时间而言，快速排序被认为是目前最好的内部排平均时间而言，快速排序被认为是目前最好的内部排序方法。快速排序适用于记录较多且基本无序的情况序方法。快速排序适用于记录较多且基本无序的情况。n由于由于排序过程中存在大跨度的数据移动，所以快速排序排序过程中存在大跨度的数据移动，所以快速排序是一种不稳定的排序方法。是一种不稳定的排序方法。51512023/3

45、/302023/3/305151自测题自测题 采用递归方式对顺序表进行快速排序采用递归方式对顺序表进行快速排序,下列关于递归次数的下列关于递归次数的叙述中叙述中,正确的是正确的是A.A.递归次数与初始数据的排列次序无关递归次数与初始数据的排列次序无关B.B.每次划分后每次划分后,先处理较长的分区可以减少递归次数先处理较长的分区可以减少递归次数C.C.每次划分后每次划分后,先处理较短的分区可以减少递归次数先处理较短的分区可以减少递归次数D.D.递归次数与每次划分后得到的分区处理顺序无关递归次数与每次划分后得到的分区处理顺序无关【20102010年全国硕士研究生入学统一考试计算机学科专业基础综合年

46、全国硕士研究生入学统一考试计算机学科专业基础综合】D (D (若要减少递归深度选若要减少递归深度选 C)C)5252自测题自测题 为了为了实现快速排序算法，待排序序列宜采用的存储方式是（实现快速排序算法，待排序序列宜采用的存储方式是（）。）。A A顺序存储顺序存储B B散列存储散列存储C C链式存储链式存储D D索引存储索引存储 【20112011年全国硕士研究生入学统一考试计算机学科专业基础综合年全国硕士研究生入学统一考试计算机学科专业基础综合】【参考答案参考答案】A A 5353下列下列选项中，不可能是快速排序第选项中，不可能是快速排序第2 2趟排序结果的是（趟排序结果的是（）。）。A A

47、2,3,5,4,6,7,92,3,5,4,6,7,9B B2,7,5,6,4,3,92,7,5,6,4,3,9C C3,2,5,4,7,6,93,2,5,4,7,6,9D D4,2,3,5,7,6,94,2,3,5,7,6,9【20142014年全国硕士研究生入学统一考试计算机学科专业基础综合】年全国硕士研究生入学统一考试计算机学科专业基础综合】【参考答案】【参考答案】C C【题目解析】每趟快速排序后，至少一个记录找到最终位【题目解析】每趟快速排序后，至少一个记录找到最终位置。置。自测题自测题 54542023/3/302023/3/305454一组记录的关键字为一组记录的关键字为4646、7

48、979、5656、3838、4040、84,84,则利用快则利用快速排序的方法速排序的方法,以第一个记录为枢轴得到的一次划分结果是以第一个记录为枢轴得到的一次划分结果是A A、3838、4040、4646、5656、7979、84 84 B B、4040、3838、4646、7979、5656、8484C C、4040、3838、4646、5656、7979、84 84 D D、4040、3838、4646、8484、5656、7979【北京交通大学北京交通大学20052005一一.8(2.8(2分分)】C C（要注意交换位置）（要注意交换位置）自测题自测题 55552023/3/302023

49、/3/305555对给定关定关键字序号字序号j(1jn),要求在无序要求在无序记录A1.n中找中找到关到关键字从小到大排在第字从小到大排在第j位上的位上的记录,写一个算法利用快速写一个算法利用快速排序的划分思想排序的划分思想实现上述上述查找。找。(要求用最少的要求用最少的时间和最少和最少的空的空间)例如：例如：给定无序关定无序关键字字7,5,1,6,2,8,9,3,当当j=4时,找到的找到的关关键字字应是是5。【中科院研究生院中科院研究生院2003十二十二(15分分)】【武武汉理工大学理工大学2002四四.3(35/3分分)】算法举例算法举例56562023/3/302023/3/305656

50、int partition(RecType A,int 1,int n)int partition(RecType A,int 1,int n)int i=1,j=n;x=Ai.key;int i=1,j=n;x=Ai.key;i=1;i=1;while(ij)while(ij)while(i=x)j-;while(i=x)j-;if(ij)Ai+=Aj;if(ij)Ai+=Aj;while(ij&Ai.key=x)i+;while(ij&Ai.key=x)i+;if(ij)Aj-=Ai;if(ij)Aj-=Ai;return i;return i;void Find_j(RecType A,