8数据结构及算法-排序.ppt

第八章排序技术,本章的基本内容是：排序的基本概念插入排序交换排序选择排序归并排序,8.1概述,排序：将一组“无序”的记录序列,调整为按关键字“有序”的记录序列.,1.排序的基本概念,排序：给定一组记录的集合r1,r2,rn，其相应的关键码分别为k1,k2,kn，排序是将这些记录排列成顺序为rs1,rs2,rsn的一个序列，使得相应的关键码满足非递减关系ks1ks2ksn（称为升序）或非递增关系ks1ks2ksn（称为降序）。,1.排序的基本概念,8.1概述,假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri一定在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。,排序算法的稳定性：,8.1概述,1.排序的基本概念,待排序序列中的记录已按关键码排好序。待排序序列中记录的排列顺序与排好序的顺序正好相反。,8.1概述,1.排序的基本概念,正序：,逆序（反序）：,排序的分类在排序的整个过程中，待排序的所有记录全部被放置在内存中,不需要访问外存由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。,8.1概述,1.排序的基本概念,1.内排序：,2.外排序：,2.内排序算法,1.插入排序2.交换排序3.选择排序4.归并排序,8.1概述,排序基本过程:是一个逐步扩大记录的有序序列长度的过程,3.排序的基本过程,有序序列区,无序序列区,有序序列区,无序序列区,一趟排序,一趟排序:将无序序列区里一个或几个记录合并到有序序列的过程为一趟排序，有序序列长度增加1个或几个,8.1概述,4.排序算法的存储结构,从操作角度看，排序是线性结构的一种操作，待排序记录可以用顺序存储结构或链接存储结构存储。,假定2：将待排序的记录序列排序为升序序列。,rn+1,假定1：待排序记录采用顺序存储结构，关键码为整型，且记录只有关键码一个数据项。,8.1概述,内排序算法,1.插入排序2.交换排序3.选择排序4.归并排序,8.1概述,8.2插入排序,插入排序的主要操作是插入，其基本思想是：每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序为止。,举例:有序序列2,待排序记录3,6,1,1）直接插入排序2）希尔排序,基本思想：在插入第i（i1）个记录时，前面的i-1个记录已经排好序。,8.2.1直接插入排序,8.2插入排序,直接插入排序过程示例,r0123456,21,18,25,22,10,25*,21,21,18,10,第五趟,算法稳定吗？,21,算法思想？,i从第2个数到第n个数将第i个数插入到有序序列中的合理位置,8.2插入排序,共多少趟？,对于ri，如何查找它的插入位置?如何实现插入？,直接插入排序,需解决的关键问题?,20,25,21,18,26,1)将ri暂存在r02)j=i-1；/从第i-1记录开始查找3)当rjr0时，循环做rj后移一个位置,j-4)rj+1=r0/将r0插入到位置j+1,22,012345,21,i,j,25,j,22,j,21,8.2插入排序,直接插入排序,20,25,10,18,25,22,012345,10,i,j,25,22,20,10,j,r0的作用?,暂存单元,监视哨,对于ri，如何查找它的插入位置?如何实现插入？,需解决的关键问题?,1)将ri暂存在r02)j=i-1；/从第i-1记录开始查找3)当rjr0时，循环做rj后移一个位置,j-4)rj+1=r0/将r0插入到位置j+1,j,j,8.2插入排序,voidinsertSort(intr,intn)for(i=2;i=1;d=d/2)以d为增量，进行组内直接插入排序；,8.2插入排序,希尔插入排序过程示例,123456789,40,21,25,49,25*,16,初始序列,30,08,13,d=4,每隔d分为一组,在整个序列中，前d个记录分别是d个子序列中的第一个记录，所以从第d+1个记录开始进行插入。,for(i=d+1;ir0，循环做：rj后移一位j-r0插入到位置j+1,将插入数据ri暂存入r0j=i-d当rjr0且j0，循环做：ri后移d位j=j-d;r0插入到位置j+d,直接插入排序：,希尔排序：,8.2插入排序,解决方法：在插入记录ri时，自ri-d起往前跳跃式（跳跃幅度为d）搜索待插入位置，并且r0只是暂存单元，不是哨兵。当搜索位置0，表示插入位置已找到。在搜索过程中，记录后移也是跳跃d个位置。在整个序列中，前d个记录分别是d个子序列中的第一个记录，所以从第d+1个记录开始进行插入。,关键问题(2)子序列内如何进行直接插入排序？,8.2插入排序,算法描述：,for(i=d+1;i0,关键问题(2)子序列内如何进行直接插入排序？,8.2插入排序,voidShellSort(intr,intn)for(d=n/2;d=1;d=d/2)/以d为增量,组内直接插入排序for(i=d+1;i0,希尔插入排序,8.2插入排序,希尔排序练习,12592063124,初始序列,第一趟结果d=3,第二趟结果d=2,第三趟结果d=1,12592063124,65920123124,56912202431,初始化：d=3，d=2d=1,8.2插入排序,希尔排序算法的时间性能,希尔排序算法的时间性能是所取增量的函数，而到目前为止尚未有人求得一种最好的增量序列。研究表明，希尔排序的时间性能在O(n2)和O(nlog2n)之间。当n在某个特定范围内，希尔排序所需的比较次数和记录的移动次数约为O(n1.3)。希尔排序不稳定,希尔排序开始时增量较大，每个子序列中的记录个数较少，从而排序速度较快；当增量较小时，虽然每个子序列中记录个数较多，但整个序列已基本有序，排序速度也较快。,8.2插入排序,第八章排序技术,本章的基本内容是：排序的基本概念插入排序交换排序选择排序归并排序,交换排序的主要操作是交换，其主要思想是：在待排序列中选两个记录，将它们的关键码相比较，如果反序（即排列顺序与排序后的次序正好相反），则交换它们的存储位置。,8.3交换排序,反序则交换,1）冒泡排序2）快速排序,8.3.1起泡排序,基本思想：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。,8.3交换排序,05,98,12,69,38,53,81,起泡排序过程示例,总共n-1趟,一共做多少趟？,for(i=1;irj+1)rjrj+1;,第i趟的比较范围：,从1到（n-i）,8.3交换排序,1234567,05,98,12,69,38,53,81,起泡排序过程示例,提问：一定需要做n-1趟？,如果在一趟排序过程中没有进行过交换操作,则排序结束。,8.3交换排序,解决方法：在每一趟起泡排序之前，令exchange的初值为0。在排序过程中，只要有记录交换，用exchange记录交换发生的位置。这样，在一趟排序结束后，只有当exchange的值不为0才需要继续做下一趟冒泡排序。,关键问题1)：如何判别起泡排序的结束？,intexchange=n;while(exchange)exchange=0;for(j=1;jrj+1)rjrj+1;exchange=j;,for(i=1;irj+1)rjrj+1;,8.3交换排序,05,98,12,69,38,53,81,起泡排序过程示例,提问：每趟排序只能使待排序范围减1吗？,8.3交换排序,05,98,12,69,78,81,30,起泡排序过程示例,如果最后一次交换是(位置j)(位置j+1)，位置j以后的所有记录均已经有序，即下一趟的待排序范围缩短为1到j,j,j+1,8.3交换排序,j,关键问题2）：如何确定每趟起泡排序的范围？,解决方法：变量exchange记载的是这趟排序中最后一次交换的位置，而下一趟的排序范围是1到exchange。,intexchange=n;while(exchange)bound=exchange;exchange=0;for(j=1;jrj+1)rjrj+1;exchange=j;,intexchange=n;while(exchange)exchange=0;for(j=1;jrj+1)rjrj+1;exchange=j;,8.3交换排序,voidBubbleSort(intr,intn)exchange=n;/初始的排序范围是所有记录while(exchange)bound=exchange;exchange=0；for(j=1;jrj+1)rjrj+1；exchange=j；,起泡排序算法,8.3交换排序,起泡排序练习,12592063124,初始序列,第一趟结果,第二趟结果,第三趟结果,第四趟结果,59126202431,59612202431,56912202431,56912202431,8.3交换排序,起泡排序的时间性能分析,最好情况：,时间复杂度为O(n)。,8.3交换排序,（正序）,最坏情况（反序）：,起泡排序的时间性能分析,最好情况（正序）：,时间复杂度为O(n)；,时间复杂度为O(n2)。,平均情况：时间复杂度为O(n2)。,稳定算法,8.3交换排序,内排序算法,1.插入排序2.交换排序3.选择排序4.归并排序,8.1概述,8.3.2快速排序,首先选一个轴值（即比较的基准），通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键码均小于或等于轴值，后一部分记录的关键码均大于或等于轴值，然后分别对这两部分重复上述方法，直到整个序列有序。,举例:3827555033304965302733385055496527303338495055652730333849505565,8.3交换排序,算法思想：,快速排序的基本思想,如何选择轴值？如何实现分割（称一次划分）？如何处理分割得到的两个待排序子序列？如何判别快速排序的结束？,需解决的关键问题?,举例:38275550333049653027333850554965,8.3交换排序,选择轴值的方法：1.使用第一个记录的关键码；2.选取序列中间记录的关键码；3.比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为轴值并调换到第一个记录的位置；4.随机选取轴值。,关键问题：如何选择轴值？,选取不同轴值的后果：决定两个子序列的长度，期望子序列的长度最好相等。,8.3交换排序,举例:38275550333049653027333850554965,27,50,38,49,55,关键问题：如何实现一次划分？,每个数和轴值做比较，比轴值大的数放后面，比轴值小的数放前面。关键在于数和轴值交换，从前、后两端开始，逐渐向中间轴值逼近的过程。,8.3交换排序,33,27,50,38,49,55,33,关键问题：如何实现一次划分？,8.3交换排序,1）当轴值在前面时，从后往前扫描，后面数逐个和轴值比较，第一个比轴值小的数和轴值换，小的数放在轴值的前面，轴值就位于待排序区域的后面2）当轴值在后面时，从前往后扫描，前面数逐个和轴值比较，第一个比轴值大的数和轴值换，大的数放在轴值的后面，轴值就位于待排序区域的前面3）当扫描到轴值，轴值就完成了一次划分,27,50,38,49,55,33,27,50,38,49,55,33,每个数和轴值做比较，比轴值大的数放后面，比轴值小的数放前面。关键在于数和轴值交换，从前后两端开始，逐渐向中间轴值逼近的过程。,27,50,38,49,55,33,完成一次划分O(n),30,65,27,50,38,49,55,关键问题：如何实现一次划分？,i=0,j=n-11)j从后往前扫描,找比轴值小的第一个数,和轴值交换2)i从前往后扫描,找比轴值大的第一个数,和轴值交换,8.3交换排序,33,关键问题：如何实现一次划分？,i=0,j=n-11)j从后往前扫描,找比轴值小的第一个数,和轴值交换2)i从前往后扫描,找比轴值大的第一个数,和轴值交换直到i=j结束，完成一次划分，即轴值的位置,8.3交换排序,38,33,38,50,30,27,33,65,49,55,解决方法：设待划分的序列是rsrt，设参数i，j分别指向子序列左、右两端的下标s和t，令rs为轴值，（1）j从后向前扫描，直到rjri，将rj移动到ri的位置(rj与ri交换)，使关键码小（同轴值相比）的记录移动到前面去；（2）i从前向后扫描，直到rirj，将ri移动到rj的位置(ri与rj交换)，使关键码大（同轴值比较）的记录移动到后面去；（3）重复上述过程，直到i=j。,关键问题：如何实现一次划分？,8.3交换排序,关键问题：如何实现一次划分？,算法描述：,intPartition(intr,intfirst,intend)i=first;j=end;/初始化while(ij)while(ij/i为轴值的最终位置,1)j从后往前扫描,找比轴值小的第一个数,和轴值交换2)i从前往后扫描,找比轴值大的第一个数,和轴值交换直到i=j结束，完成一次划分，即轴值的位置,3827551349,1327553849,8.3交换排序,解决方法：对分割得到的两个子序列递归地执行快速排序。,关键问题：如何处理分割得到的两个待排序子序列？,8.3交换排序,33,33,解决方法：若待排序列中只有一个记录，显然已有序，否则进行一次划分后，再分别对分割所得的两个子序列进行快速排序（即递归处理）。,关键问题：如何判别快速排序的结束？,8.3交换排序,33,33,快速排序的过程,第一趟,第二趟,第三趟,8.3交换排序,30,65,27,50,38,49,55,33,33,33,voidQuickSort(intr,intfirst,intend)/在序列firstend中递归地进行快速排序if(firstend)pivotpos=Partition(r,first,end);QuickSort(r,first,pivotpos-1);QuickSort(r,pivotpos+1,end);,算法描述：,关键问题：如何判别快速排序的结束？,3827551349,1327385549,pivotpos,8.3交换排序,快速排序练习,12592063124,初始序列,第一趟结果,第二趟结果,第三趟结果,65912203124,56912203124,56912202431,8.3交换排序,i=0,j=n-11)j从后往前扫描,找比轴值小的第一个数,和轴值交换2)i从前往后扫描,找比轴值大的第一个数,和轴值交换直到i=j结束，完成一次划分，即轴值的位置,8.3交换排序,思考:12345第一趟：2345第二趟：2345第三趟：2345第四趟：2345,快速排序的时间性能分析,例：38,6,27,55,50,13,49的快速排序递归树如下：,快速排序的递归执行过程可以用递归树描述。,快速排序的时间性能分析,8.3交换排序,第一趟结果,1362738505549,第二趟结果,6132738495055,最好情况：每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为O(nlog2n)。,快速排序的时间性能分析,T(n)2T(n/2)n2(2T(n/4)n/2)n4T(n/4)2n4(2T(n/8)n/4)2n8T(n/8)3nnT(1)nlog2nO(nlog2n),8.3交换排序,最坏情况：每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空），为O(n2)。,最好情况：每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为O(nlog2n)。,快速排序的时间性能分析,平均情况：为O(nlog2n)。,不稳定算法,1,2,3,4,5,8.3交换排序,5,7,3,2,2*,内排序算法,1.插入排序2.交换排序3.选择排序4.归并排序,8.1概述,选择排序的主要操作是选择，其主要思想是：每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。,8.4选择排序,8.4.1简单选择排序,基本思想：第i趟在n-i+1（i=1,2,n-1）个记录中选取关键码最小的记录作为有序序列中的第i个记录。,举例：212549281608,082549281621,8.4选择排序,简单选择排序示例,i=2,21,28,i=1,25,16,49,08,08,i=3,21,16,i=4,8.4选择排序,i=4,i=5,简单选择排序示例,25,28,for(i=1;in;i+)/从第i个数到第n个数中，选出最小的数和第i个数换,总共执行多少趟？,每趟做什么？,8.4选择排序,设置一个整型变量index，Index初始为i。rindex逐一和后面的数比较，记录在一趟比较过程中关键码最小的记录的下标。,关键问题：如何在无序区（第i个数-第n个数）中选出关键码最小的记录？,21,28,25,16,49,08,index,index,index=i;for(j=i+1;j=1;i-)/初建堆sift(r,i,n);for(i=1;in;i+)r1rn-i+1;/移走堆顶sift(r,1,n-i);/重建堆,8.4选择排序,堆排序过程,12592063124,初建堆:根据待排序序列构建一个堆，输出堆的层序序列,初始堆:31202456912,8.4选择排序,堆排序练习,12592063124,每一趟：堆顶结点和树上最后一个结点换，最后一个结点断链，再调整为一个堆，输出堆的层序遍历,第一趟排序:24201256931,8.4选择排序,堆排序练习,12592063124,第二趟,31,6,5,第二趟排序:20912562431,8.4选择排序,每一趟：堆顶结点和树上最后一个结点换，最后一个结点断链，再调整为一个堆，输出堆的层序遍历,堆排序练习,12592063124,第三趟,第三趟排序:12965202431,8.4选择排序,堆排序练习,12592063124,第四趟,第四趟排序:95612202431,8.4选择排序,堆排序练习,12592063124,第五趟,第六趟结果,第五趟排序:65912202431,第六趟排序:56912202431,8.4选择排序,堆排序练习,12592063124,初始序列,初始堆:31202456912,第一趟排序:24201256931,第二趟排序:20912562431,第三趟排序:12965202431,第四趟排序:95612202431,第五趟排序:65912202431,第六趟排序:56912202431,8.4选择排序,堆排序算法的性能分析,第1个for循环是初始建堆，需要O(n)时间；第2个for循环是输出堆顶重建堆，共需要取n-1次堆顶记录，第i次取堆顶记录重建堆需要O(log2i)时间，需要O(nlog2n)时间；因此整个时间复杂度为O(nlog2n)，这是堆排序的最好、最坏和平均的时间代价。算法不稳定,8.4选择排序,内排序算法,1.插入排序2.交换排序3.选择排序4.归并排序,8.1概述,归并排序,归并排序的主要操作是归并，其主要思想是：将若干有序序列逐步归并，最终得到一个有序序列。,8.5归并排序,归并：将两