数据结构及算法排序ppt课件.ppt

第八章 排序技术,本章的基本内容是：,排序的基本概念,插入排序,交换排序,选择排序,归并排序,8.1,概 述,排序：,将一组,“无序”,的,记录序列,调整为,按关键字,“有序”,的记录序列,.,学号,姓名,高数,英语,思想品德,000,2,王 军,85,88,000,1,李 明,64,92,0003,汤晓影,85,86,68,72,78,1.,排序的基本概念,排序：,给定一组,记录,的集合,r,1,r,2,r,n,，,其相应的,关键码,分别为,k,1,k,2,k,n,，,排序是将这些记录排列成顺序为,r,s,1,r,s,2,r,sn,的一个序列，使得相应的,关键码,满足,非递减关系,k,s,1,k,s,2,k,sn,（,称为,升序,）或非递增关系,k,s,1,k,s,2,k,sn,（,称为,降序,）。,1.,排序的基本概念,学号,姓名,高数,英语,000,2,李 明,64,000,1,王 军,85,0003,汤晓影,85,72,68,78,学号,姓名,高数,英语,0001,王 军,85,0002,李 明,64,0003,汤晓影,85,68,72,78,8.1,概 述,假定在待排序的记录集中，存在,多个具有相同键值,的记录，若经过排序，这些记录的,相对次序,仍然保持不变，即在原序列中，,k,i,=,k,j,且,r,i,在,r,j,之前，,而在排序后的序列中，,r,i,一定在,r,j之前,，则称这种排序算法是,稳定的,；否则称为,不稳定的,。,学号,姓名,高数,英语,思想品德,0001,王 军,85,88,0002,李 明,64,92,0003,汤晓影,85,86,68,72,78,排序算法的稳定性：,8.1,概 述,1.,排序的基本概念,待排序序列中的记录已按关键码,排好序,。,待排序序列中记录的排列顺序与排好序的顺序,正好相反,。,学号,姓名,高数,英语,思想品德,0001,王 军,85,88,0002,李 明,64,92,0003,汤晓影,85,86,68,72,78,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,概 述,10 15 24 6 12,35,40 98,0,1 2 3 4 5 6 7 8,内排序算法,1.,插入排序,2.,交换排序,3.,选择排序,4.,归并排序,直接插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,堆排序,8.1,概 述,8.2,插入排序,插入排序的主要操作是,插入,，其基本思想是：每次将一个,待排序的记录,按其关键码的大小插入到一个已经排好序的,有序序列,中，,直到,全部记录排好序为止。,举例,:,有序序列,2,待排序记录,3,6,1,1,）直接插入排序,2,）希尔排序,基本思想,：在插入第,i,（,i,1,）个记录时，前面的,i,-1,个记录已经排好序。,8.2.1,直接插入排序,有序序列,无序序列,r,1,r,2,r,i,-1,r,i,r,n,r,i+,1,r,1,r,2,r,i,-1,r,i,r,n,r,i+,1,有序序列,无序序列,82,插入排序,直接插入排序过程示例,r,0,1 2 3 4 5 6,21,18,25,22,10,25*,21,第一趟,18,22,10,25*,25,25,22,21,25,22,21,10,25,*,25,22,21,10,25,*,25,22,21,18,10,18,10,25*,第二趟,18,第四趟,18,25,*,第三趟,第五趟,算法稳定吗？,21,算法思想？,i,从第,2,个数到,第,n,个数,将第,i,个数插入,到有序序列中的合理位置,8.2,插入排序,共多少趟？,对于,ri,，如何查找它的,插入位置,?,如何,实现插入,？,直接插入排序,需解决的关键问题,?,无序序列,20,25,21,18,26,1),将,ri,暂存在,r0,2)j=i-1,；,/,从第,i-1,记录开始查找,3),当,rjr0,时，循环做,rj,后移一个位置,j-,4)r,j+1,=r0 /,将,r0,插入到位置,j+1,22,0,1 2 3 4 5,21,i,j,25,j,22,j,21,8.2,插入排序,直接插入排序,无序序列,20,25,10,18,25,22,0,1 2 3 4 5,10,i,j,25,22,20,10,j,r0,的作用,?,暂存单元,监视哨,对于,ri,，如何查找它的,插入位置,?,如何,实现插入,？,需解决的关键问题,?,1),将,ri,暂存在,r0,2)j=i-1/,从第,i-1,记录开始查找,3),当,rjr0,时，循环做,rj,后移一个位置,j-,4)r,j+1,=r0 /,将,r0,插入到位置,j+1,j,j,8.2,插入排序,void insertSort(int r,int n),for(i=2;i=n;i+),r0=ri;,for(j=i-1;r0r0,时，循环做：,rj,后移一个位置,j-,1.4 r,j+1,=r0,8.2,插入排序,直接插入排序过程示例,r,0,1 2 3 4 5 6,21,18,25,22,10,25*,21,21,25,i,=2,18,22,10,25*,25,i,=3,18,22,10,25*,22,25,22,21,10,25,22,21,10,25,25,*,25,22,21,10,25,*,25,22,21,18,10,18,18,10,25*,i,=4,18,i,=6,18,25,*,i,=5,25,21,8.2,插入排序,直接插入排序练习,12 5 9 20 6 31 24,8.2,插入排序,直接插入排序练习,12 5 9 20 6 31 24,初始序列,5,12 9 20 6 31 24,第一趟,5,9,12 20 6 31 24,第二趟,5 9 12,20,6 31 24,第三趟,5,6,9 12 20 31 24,第四趟,第五趟,5 6 9 12 20,31,24,第六趟,5 6 9 12 20,24,31,8.2,插入排序,1.,基本操作,。内排序在排序过程中的基本操作：,比较,：关键码之间的比较；,移动,：记录从一个位置移动到另一个位置。,2.,辅助存储空间,。,辅助存储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。,3.,算法本身的复杂程度,。,排序,算法的性能,8.2,插入排序,直接插入排序算法性能分析,最好情况下：,1,2,3,4,5,时间复杂度为,O,(,n,)。,比较次数：,n,-1,移动次数：,2(,n,-1),1,2,3,4,5,2,1,2,3,4,5,3,1,2,3,4,5,4,1,2,3,4,5,5,（正序）,8.2,插入排序,直接插入排序算法性能分析,最好,情况下（正序）：,比较次数：,n,-1,移动次数：,2(,n,-1),最坏,情况下（逆序）：,时间复杂度为,O,(,n,2,)。,5,4,3,2,1,4,5,3,2,1,4,3,4,5,2,1,3,2,3,4,5,1,2,1,2,3,4,5,1,比较次数：,移动次数：,2,),1,)(,2,(,2,-,+,=,=,n,n,i,n,i,2,),1,)(,4,(,1,-,+,=,+,n,n,i,n,2,=,i,）,（,时间复杂度为,O,(,n,)。,8.2,插入排序,平均,情况下（随机排列）：,直接插入排序算法性能分析,时间复杂度为,O,(,n,2,)。,比较次数：,移动次数：,4,),1,)(,4,(,-,+,=,n,n,n,2,=,i,4,),1,)(,2,(,2,-,+,=,=,n,n,n,i,i,2,（,2,1,+,i,）,8.2,插入排序,空间性能：,需要一个记录的辅助空间。,直接插入排序算法是一种,稳定,的排序算法。,直接插入排序算法性能分析,直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。,当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的,效率降低,。,8.2,插入排序,8.2.2,希尔排序,改进的着眼点：,（,1,）由于直接插入排序算法简单，在待排序记录数量n,较小,时效率也很高。,（,2,）若待排序记录按关键码,基本有序,时，直接插入排序的效率可以大大提高；,2,1,3,5,4,3,2,1,8.2,插入排序,（,1,）应如何分割待排序记录，才能保证整个序列逐步向基本有序发展？,（,2,）子序列内如何进行直接插入排序？,需解决的关键问题,?,基本思想：,将整个待排序记录,分割,成若干个,子序列,，在,子序列内,分别进行,直接插入排序,，待整个序列中的记录,基本有序,时，对,全体记录,进行直接插入排序。,8.2.2,希尔排序,20 18 19,6 5 7,1 3 2,20,18,19,6,5,7,1,3,2,8.2,插入排序,8.2.2,希尔排序子序列的构成不能是简单地“逐段分割”，而是将,相距某个“增量”的记录,组成一个子序列。,逐渐,缩短“增量”,，当缩短为,1,时就是对全体记录进行排序。,10,2,6,15,9,1,8,20,4,11,10,2,6,15,9,1,8,20,4,11,d=3,基本思想：,将整个待排序记录,分割,成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的记录,基本有序,时，对全体记录进行直接插入排序。,8.2,插入排序,希尔插入排序过程示例,1 2 3 4 5 6,7 8 9,40,21,25,49,25*,16,初始序列,30,08,13,d=4,21,25,25*,30,49,08,40,16,13,25,2,1,25*,30,08,49,13,16,40,d=2,13,25,2,1,08,25*,16,30,49,40,25,21,25*,30,08,13,16,40,49,d=1,08,25,21,13,25*,16,30,40,49,08,25,13,16,21,25*,40,30,49,每隔,d-1,个增量记录,分为一组,每组内采用直接插入排序,8.2,插入排序,算法稳定吗？,解决方法：,将相隔某个“增量”的记录组成一个子序列。,增量应如何取？,希尔最早提出的方法是,d,1,=n/2，d,i+1,=d,i,/2。,关键问题(1)应如何分割待排序记录？,算法描述：,ford=n/2;d=1;d=d/2),以,d,为增量，进行组内直接插入排序；,8.2,插入排序,希尔插入排序过程示例,1 2 3 4 5 6,7 8 9,40,21,25,49,25*,16,初始序列,30,08,13,d=4,21,25,25*,30,49,08,40,16,13,25,2,1,25*,30,08,49,13,16,40,每隔,d,分为一组,在整个序列中，前,d,个记录分别是,d,个子序列中的第一个记录，所以从第,d+1,个记录开始进行插入。,for(i=d+1;ir0,，循环做：,rj,后移一位,j-,r0,插入到位置,j,+1,将插入数据,ri,暂存入,r0,j=,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&r0=1;d=d/2)/,以,d,为增量,组内直接插入排序,for(i=,d+1,;i0&r0rj),rj,+d,=rj;/,记录后移,d,个位置,j=j,-d,;/,比较同一子序列的前一个记录,rj,+d,=r0;,希尔插入排序,8.2,插入排序,希尔排序练习,12,5,9,20,6,31,24,初始序列,第一趟,结果,d=3,第二趟,结果,d=2,第三趟,结果,d=1,12,5,9,20,6,31,24,6 5 9 20 12 31 24,5 6 9 12 20 24 31,初始化：,d=3,，,d=2,d=1,8.2,插入排序,希尔排序算法的时间性能,希尔排序算法的时间性能是所取,增量,的函数，而到目前为止尚未有人求得一种最好的增量序列。,研究表明，希尔排序的,时间性能,在,O,(,n,2,),和,O,(,nlog,2,n,),之间。当,n,在某个特定范围内，希尔排序所需的比较次数和记录的移动次数约为,O,(,n,1,.,3,),。,希尔排序,不稳定,希尔排序开始时,增量较大,，每个子序列中的,记录个数较少,，从而排序速度较快；当,增量较小,时，虽然每个子序列中,记录个数较多,，但整个序列已,基本有序,，排序速度也较快。,8.2,插入排序,第八章 排序技术,本章的基本内容是：,排序的基本概念,插入排序,交换排序,选择排序,归并排序,交换排序的主要操作是,交换,，其主要思想是：在待排序列中选,两个,记录，将它们的关键码相比较，如果,反序,（即排列顺序与排序后的次序正好相反），则,交换,它们的存储位置。,8.3,交换排序,反序则 交换,r,i,r,j,1,）冒泡排序,2,）快速排序,8.3.1,起泡排序,基本思想：,两两比较,相邻,记录的关键码，如果,反序,则交换，直到没有反序的记录为止。,r,j,r,j,+1,r,i,+1,r,n,-,1,r,n,无序区 有序区,1,j,i,-,1,已经位于最终位置,反序则交换,8.3,交换排序,05,98,12,69,38,53,81,起泡排序过程示例,05,98,12,69,38,53,81,05,98,12,69,38,53,81,05,9812,69,38,53,81,总共,n-1,趟,一共做多少趟？,for(i=1;i=n-1;i+),for(j=,1,;jrj+1),rj,rj+1;,第,i,趟的比较范围：,从,1,到（,n-i,）,8.3,交换排序,1 2 3 4 5 6 7,05,98,12,69,38,53,81,起泡排序过程示例,05,98,12,69,38,53,81,05,98,12,69,38,53,81,05,98,12,69,38,53,81,提问：,一定,需要做,n-1,趟？,如果在一趟排序过程中没有进行过交换操作,则排序结束。,8.3,交换排序,解决方法：,在,每一趟起泡排序,之前，令,exchange,的,初值为,0,。,在排序过程中，只要有记录交换，用,exchange,记录交换发生的位置,。这样，在一趟排序结束后，只有,当,exchange,的值不为,0,才需要继续做下一趟冒泡排序。,关键问题,1),：,如何判别起泡排序的结束？,int exchange=n;,while,(,exchange,),exchange=0;,for(j=1;jrj+1),rjrj+1;,exchange=j;,for(i=1;i=n-1;i+),for(j=1;jrj+1),rjrj+1;,8.3,交换排序,05,98,12,69,38,53,81,起泡排序过程示例,05,98,12,69,38,53,81,05,98,12,69,38,53,81,05,98,12,69,38,53,81,提问：每,趟排序只能使,待排序范围,减,1,吗？,8.3,交换排序,05,98,12,69,78,81,30,起泡排序过程示例,05,98,12,30,69,78,81,05,98,12,30,69,78,81,如果最后一次交换,是,(,位置,j)(,位置,j+1),，,位置,j,以后的所有记录均已经有序，,即下一趟的待排序范围缩短为,1,到,j,j,j+1,8.3,交换排序,j,关键问题,2,）：如何确定,每趟,起泡排序的范围？,解决方法：,变量,exchange,记载的是这趟排序中,最后一次交换的位置而,下一趟的排序范围,是,1,到,exchange,。,int exchange=n;,while,(,exchange,),bound=exchange;,exchange=0;,for(j=,1,;,jrj+1),rjrj+1;,exchange=j;,int exchange=n;,while,(,exchange,),exchange=0;,for(j=1;jrj+1),rjrj+1;,exchange=j;,8.3,交换排序,void BubbleSort,(,int r,int n,),exchange=n;/,初始的排序范围是所有记录,while,(,exchange,),bound=exchange;,exchange=0；,for,(,j=1;jrj+1,),rjrj+1；,exchange=j；,起泡排序算法,8.3,交换排序,起泡排序练习,12 5 9 20 6 31 24,初始序列,第一趟结果,第二趟结果,第三趟结果,第四趟结果,5 9 12 6 20 24,31,5 9 6,12 20,24,31,5 6 9 12,20,24,31,5 6,9,12 20,24,31,8.3,交换排序,起泡排序的时间性能分析,最好情况：,比较次数：,n,-1,移动次数：,0,1,2,3,4,5,时间复杂度为,O,(,n,),。,1,2,3,4,5,8.3,交换排序,（正序）,最坏情况（反序）：,起泡排序的时间性能分析,最好情况（正序）：,比较次数：,n,-1,移动次数：,0,5,4,3,2,1,时间复杂度为,O,(,n,)；,时间复杂度为,O,(,n,2,)。,4,3,2,1,5,3,2,1,4,5,2,1,3,4,5,1,2,3,4,5,比较次数：,移动次数：,2,),1,(,1,-,=,=,n,n,(,n,-,i,),n,-1,i,2,),1,(,1,-,=,=,n,3n,3,(,n,-,i,),n,-1,i,平均情况：,时间复杂度为,O,(,n,2,)。,稳定算法,8.3,交换排序,内排序算法,1.,插入排序,2.,交换排序,3.,选择排序,4.,归并排序,直接插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,堆排序,8.1,概 述,8.3.2,快速排序,首先选一个,轴值,（即,比较的基准,），通过一趟排序将待排序记录,分割,成独立的,两,部分，前一部分记录的关键码均,小于或等于,轴值，后一部分记录的关键码均,大于或等于,轴值，然后分别对这,两部分重复上述方法,，直到整个序列有序。,举例,:,38,27 55,50 33 30,49 65,30,27,33,38,50,55 49,65,27,30,33,38,49,50,55,65,27,30,33,38,49,50,55,65,8.3,交换排序,算法思想：,快速排序的基本思想,如何选择轴值？,如何实现,分割,（称一次划分）？,如何处理分割得到的两个待排序子序列？,如何判别快速排序的,结束,？,需解决的关键问题,?,举例,:,38,27 55 50 33 30 49 65,30,27 33,38,50,55 49 65,8.3,交换排序,选择轴值的方法：,1.,使用,第一个记录,的关键码；,2.,选取序列,中间记录,的关键码；,3.,比较序列中,第一个记录,、,最后一个记录,和,中间记录,的关键码，取关键码,居中,的作为轴值并调换到第一个记录的位置；,4.,随机,选取轴值。,关键问题：,如何选择轴值？,选取不同轴值的后果：,决定两个子序列的长度，期望子序列的长度最好相等。8.3,交换排序,举例,:,38,27 55 50 33 30 49 65,30,27 33,38,50,55 49 65,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,j,i,38,55,关键问题：,如何实现一次划分？,j,j,i,i,i,j,i,j,i=0,j=n-1,1)j,从后往前,扫描,找比轴值,小,的第一个数,和轴值交换,2,)i,从前往后,扫描,找比轴值,大,的第一个数,和轴值交换,8.3,交换排序,33,30,38,65,27,50,49,55,33,30,65,27,50,49,33,关键问题：,如何实现一次划分？,i=0,j=n-1,1)j,从后往前,扫描,找比轴值,小,的第一个数,和轴值交换,2,)i,从前往后,扫描,找比轴值,大,的第一个数,和轴值交换,直到,i=j,结束，完成一次划分，即,轴值的位置,8.3,交换排序,38,55,i,j,30,65,27,50,49,33,j,38,33,30,65,27,50,49,55,i,j,i,38,50,30,27,33,65,49,55,i,j,j,解决方法：,设待划分的序列是,rs rt，,设参数,i，j,分别指向子序列左、右两端的下标,s,和,t，,令,rs,为轴值，,（1）,j,从后,向前,扫描，直到,rjri,，,将,rj,移动到,ri,的位置,(rj,与,ri,交换,),，使关键码小（同轴值相比）的记录移动到前面去；,（2）,i,从前,向后,扫描，直到,rirj,，,将,ri,移动到,rj,的位置,(ri,与,rj,交换,),，使关键码大（同轴值比较）的记录移动到后面去；,（3）重复上述过程，直到,i=j,。,关键问题：,如何实现一次划分？,8.3,交换排序,关键问题：,如何实现一次划分？,算法描述：,int Partition(int r,int first,int end),i=first;j=end;/,初始化,while(ij),while(ij&ri=rj)j-,；,/,右侧扫描,if(ij),rirj;i+;/,将较小记录交换到前面,while(ij&ri=rj)i+,；,/,左侧扫描,if(ij),rjri;j-;/,将较大记录交换到后面,return i;/i,为轴值的最终位置,1)j,从后往前,扫描,找比轴值,小,的第一个数,和轴值交换,2)i,从前往后,扫描,找比轴值,大,的第一个数,和轴值交换,直到,i=j,结束，完成一次划分，即轴值的位置,38,27 55 13 49,13,27 55,38,49,8.3,交换排序,解决方法：,对分割得到的,两个子序列,递归地,执行快速排序。,关键问题：如何处理分割得到的两个待排序子序列？,30,27,50,38,49,55,65,i,j,i,j,30,27,38,65,50,49,55,8.3,交换排序,33,33,解决方法：,若待排序列中,只有一个记录,，显然已有序，否则进行一次划分后，再分别对分割所得的两个子序列进行快速排序（即递归处理）。,关键问题：,如何判别快速排序的结束？,i,j,8.3,交换排序,30,27,38,65,50,49,55,33,30,27,38,65,50,49,55,33,快速排序的过程,第一趟,第二趟,第三趟,8.3,交换排序,30,65,27,50,38,49,55,33,38,50,30,27,33,65,49,55,30,27,38,65,50,49,55,33,30,27,38,65,50,49,55,33,void QuickSort(int r,int first,int end),/,在序列,firstend,中递归地进行快速排序,if(first end),pivotpos,=Partition(r,first,end);,QuickSort(r,first,pivotpos-1,);,QuickSort(r,pivotpos+1,end,);,算法描述：,关键问题：,如何判别快速排序的结束？,38,27 55 13 49,13 27,38,55 49,pivotpos,8.3,交换排序,快速排序练习,12 5 9 20 6 31 24,初始序列,第一趟结果,第二趟结果,第三趟结果,6 5 9,12,20 31,24,5,6,9,12 20,31 24,5,6,9,12 20,24,31,8.3,交换排序,i=0,j=n-1,1)j,从后往前,扫描,找比轴值,小,的第一个数,和轴值交换,2)i,从前往后,扫描,找比轴值,大,的第一个数,和轴值交换,直到,i=j,结束，完成一次划分，即,轴值的位置,8.3,交换排序,思考,:,1 2 3 4 5,第一趟：,2 3 4 5,第二趟：,2,3,4,5,第三趟：,2,3 4 5,第四趟：,2,3,4,5,快速排序的时间性能分析,例：,38,6,27,55,50,13,49,的快速排序递归树如下：,38,13,50,55,49,6,27,快速排序的递归执行过程可以用递归树描述。,快速排序的时间性能分析,8.3,交换排序,第一趟结果,13 6 27,38,50 55 49,第,二,趟,结果,6,13,27,38,49,50,55,最好情况：,每一次划分对一个,记录定位,后，该记录的左侧子表与右侧子表的长度相同，为,O,(,n,log,2,n,)。,快速排序的时间性能分析,T,(,n,)2,Tn,/2),n,2(2,T,(,n,/4),n,/2),n,4,T,(,n,/4),2,n,4(2,T,(,n,/8),n,/4),2,n,8,T,(,n,/8),3,n,nT,(1),n,log,2,n,O,(,n,log,2,n,),8.3,交换排序,最坏情况：,每次划分只得到一个比上一次划分,少一个记录,的子序列（另一个子序列为空），为,O,(,n,2,)。,最好情况：,每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为,O,(,n,log,2,n,)。,快速排序的时间性能分析,平均情况：,为,O,(,n,log,2,n,)。,),(,),1,(,2,1,2,1,1,n,O,n,n,i,n,n,i,=,-,=,-,-,=,）,（,不稳定算法,1,2,3,4,5,8.3,交换排序,5,7,3,2,2*,内排序算法,1.,插入排序,2.,交换排序,3.,选择排序,4.,归并排序,直接插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,堆排序,8.1,概 述,选择排序的主要操作是,选择,，其主要思想是：每趟排序在,当前待排序序列,中选出关键码,最小,的记录，添加到有序序列中。,8.4,选择排序,有序序列,r,1,r,2,r,i,-1,r,i,r,n,r,k,无序序列,r,n,r,i+,1,r,1,r,2,r,i,-1,r,i,r,i,交换,最小记录,8.41,简单选择排序,基本思想：,第,i,趟在,n,-,i,+1,（,i,=1,2,n,-,1,）,个记录中选取,关键码最小,的记录作为有序序列中的,第,i,个记录,。,举例：,21,25 49 28 16,08,08,25,49 28 16 21,8.4,选择排序,简单选择排序示例,08,21,i,=2,21,28,i,=1,25,16,49,08,08,i,=3,21,08,28,49,21,28,49,16,25,16,16,25,i,=4,49,21,08,28,16,25,8.4,选择排序,i,=4,i,=5,简单选择排序示例,49,21,08,28,16,25,25,49,21,0816,28,25,28,49,21,08,16,28,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,index=i;,for,(,j=,i+1,;j=n;j+,),if,(,rjrindex),index=j;,j,8.4,选择排序,解决方法：,第,i,趟简单选择排序的待排序区间是,ri rn，,则,ri,是无序,区第一个记录，所以，将,index,所记载的关键码,最小的记录与,ri,交换,。,关键问题：选出无序区（第,i,个数,-,第,n,个数）中关键码最小的记录后，和第,i,个数交换,算法描述：,if,(,index!=i,),ririndex;,8.4,选择排序,void selectSort(int r,int n),for(i=1;in;i+),index=i;,for(j=i+1;j=n;j+),if (rjrindex)index=j;,if(,index!=i,)ririndex;,简单选择排序算法,8.4,选择排序,简单选择排序练习,12 5 9 20 6 31 24,初始序列,第一趟结果,第二趟结果,第三趟结果,5,12 9 20 6 31,24,5,6,9 20 12 31,24,5,6,9,20 12 31,24,第四趟结果,5,6,9,12,20 31,24,第五趟结果,5,6,9,12,20,31,24,第六趟结果,5,6,9,12,20,24,31,8.4,选择排序,简单选择排序算法的性能分析,移动次数：,最好情况（正序）：,0次,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,23,4,8.4,选择排序,最坏情况：,3,(,n,-1),次,简单选择排序算法的性能分析,移动次数：,最好情况（正序）：,0次,空间性能：,需一个辅助空间。,稳定性：,是一种,不稳定,的排序算法。,4,5,2,3,1,1,5,2,3,4,1,2,5,3,4,1,2,3,5,4,1,2,3,4,5,1,2,3,4,比较次数：,),(,),1,(,2,1,2,1,1,n,O,n,n,i,n,n,i,=,-,=,-,-,=,）,（,简单选择排序的时间复杂度为,O,(,n,2,),。,例如：,3 3*5 1,8.4,选择排序,内排序算法,1.,插入排序,2.,交换排序,3.,选择排序,4.,归并排序直接插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,堆排序,8.1,概 述,堆的定义,堆是具有下列性质的,完全二叉树,：,每个结点的值都,大于或等于,其,左右孩子,结点的,值，称为,大根,堆,。,50,38,45,40,28,36,32,20,18,28,大,根堆的根结点是所有结点的,最大者,。,8.4,选择排序,8.4.2,堆排序,堆的存储,对结点,i,，,2i,为其左孩子，,2i+1,为右孩子，,i/2,为双亲,50,38,45,40,28,36,32,20,18,28,50 38 45 32 36 40 28 20 18 28,1 2 3 4 5 6 7 8 9 10,采用顺序存储,8.4,选择排序,1,2,3,4,5,6,7,8,9,10,堆调整,提问：,在一棵完全二叉树中，假设,根结点,的,左右子树均是堆,，如何调整,根结点,，使,整个完全二叉树,为一个,堆,？,28,36,32,16,18,34,如果结点小于左右孩子，则与左右孩子中大的交换。,注意要自,堆顶,到,叶子,的进行调整,这个过程称为一次,筛选。,32,16,18,36,34,28,32,16,18,34,36,28,8.4,选择排序,堆调整,提问：,在一棵完全二叉树中，假设,根结点,的,左右子树均是堆,，如何调整,根结点,，使,整个完全二叉树,为一个,堆,？,28,30,32,16,18,24,30,16,18,24,32,28,8.4,选择排序,void sift(int r,int k,int m,),/,要筛选结点的编号为,k,，,堆中最后一个结点的编号为,m,i=k;j=2*i;,while(j=m)/,筛选还没有进行到叶子,if(jrj)break;,else,rirj;,i=j;j=2*i,;,堆调整,算法描述：,28,36,32,16,18,34,i,k,j,8.4,选择排序,关键,问题：,如何,由一个无序序列建成一个堆？,28,25,16,32,18,36,32,36,28,16,18,25,初始待排序序列,:28,25,16 36 18 32,8.4,选择排序,关键,问题如何,由一个无序序列建成一个堆？,28,25,16,32,18,36,16,32,16,28,25,18,36,25,32,16,28,18,36,25,28,32,36,28,16,18,25,从,最后一个非叶子结点,开始到,根结点,结束：,将,以此结点为根的子树,调整为堆，调整的过程就是,一次筛选的过程,。,初始序列,:28,25,16 36 18 32,8.4,选择排序,提问：为什么,采用这个,方法？,算法描述：,for(i=n/2;i=1;i-),sift(r,i,n);,选择排序,关键问题：,如何由一个无序序列建成一个堆？,最后一个结点（叶子）的序号是,n,，,则最后一个分支结点即为结点,n,的双亲，,其序号是,n,/2,。,首先将待排序的记录序列,构造成一个堆,，此时，选出了堆中所有记录的,最大者,，然后将它从堆中移走，并将剩余的记录再,调整成堆,，这样又找出了次大的记录，以此类推，,直到堆中只有一个记录,。,堆排序,待排序序列,:28 36 16 25 18 32,8.4,选择排序,基本思想：,算法步骤：,1,）根据待排序序列初始构造一个堆,2,）堆上结点数大于,1,时循环做：,堆,顶结点和树上最后一个结点,换，最后一个结点断链，再调整为一个堆。,堆排序,36,32,28,16,18,25,待排序序列,:28 36 16 25 18 32,36,32,16,28,