第7章-排序-Sorting第3章课件

第7章排序Sorting[严陈]第3章第7章排序Sorting1内容提要排序的基本概念排序算法的分析插入排序(直接,二分)交换排序(冒泡,快速)选择(selection,堆排序)归并(merge)基数排序内容提要排序的基本概念2基本概念排序：将一组杂乱无章的数据按一定的规律顺次排列起来。数据表(datalist):它是待排序数据对象的有限集合。排序码(key):通常数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。基本概念排序：将一组杂乱无章的数据按一定的规律顺次排列起来。3分类内排序与外排序内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。分类内排序与外排序4排序算法的稳定性如果在对象序列中有两个对象r[i]和r[j],它们的排序码k[i]==k[j],

稳定的:排序前后,对象r[i]和r[j]的相对位置不变

不稳定:else排序算法的稳定性如果在对象序列中有两个对象r[i]和r[j]5算法评价时间开销:排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象排序码序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算空间开销：算法执行时所需的附加存储算法评价时间开销:6插入排序插入排序7第7章-排序-Sorting第3章课件8第7章-排序-Sorting第3章课件9直接插入排序直接插入排序10直接插入排序直接插入排序11直接插入排序:算法分析设待排序对象个数为n,则该算法的主程序执行n-1趟排序码比较次数和对象移动次数与对象排序码的初始排列有关最好情况下,排序前对象有序 比较(KCN):n-1;移动次数(RMN):为2(n-1)最坏情况下,第i趟时第i个对象必须与前面i个对象都做排序码比较,并且每做1次比较就要做1次数据移动。

直接插入排序:算法分析设待排序对象个数为n,则该算法的主程序12在平均情况下的排序码比较次数和对象移动次数约为n2/4。因此，直接插入排序的时间复杂度为o(n2)

直接插入排序是一种稳定的排序方法在平均情况下的排序码比较次数和对象移动次数约为n2/4。因此13二分插入排序(BinaryInsertsort)

基本思想是:设在顺序表中有一个对象序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已经排好序的对象。在插入V[i]时,利用二分搜索法寻找V[i]的插入位置。二分插入排序(BinaryInsertsort)基本思14二分插入排序二分插入排序15二分插入排序:分析二分搜索比顺序搜索查找快,所以二分插入排序就平均性能来说比直接插入排序要快。它所需的排序码比较次数与待排序对象序列的初始排列无关,仅依赖于对象个数。在插入第i个对象时,需要经过log2i+1次排序码比较,才能确定它应插入的位置。因此,将n个对象(为推导方便,设为n=2k)用折半插入排序所进行的排序码比较次数为二分插入排序是一个稳定的排序方法。二分插入排序:分析二分搜索比顺序搜索查找快,所以二分插入排序16当n较大时,总排序码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况要差。在对象的初始排列已经按排序码排好序或接近有序时,直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排序的对象移动次数与直接插入排序相同,依赖于对象的初始排列当n较大时,总排序码比较次数比直接插入排序的最坏情况要好得17使用链表插入排序每插入一个对象，最大排序码比较次数等于链表中已排好序的对象个数最小排序码比较次数为1

故总的排序码比较次数最小为(n-1)最大为移动次数为0空间增加了指针域,和头结点使用链表插入排序每插入一个对象，最大排序码比较次数等于链表18交换排序交换排序19交换排序数据两两比较，逆序交换，直到全部有序冒泡，快速交换排序数据两两比较，逆序交换，直到全部有序20冒泡排序(BubbleSort)对象个数n。最多作最多作n-1趟，i=1,2,…,n-1i趟中从后向前j=n-1,n-2,……,i，顺次两两比较比较如果发生逆序，则 交换V[j-1]和V[j]。冒泡排序(BubbleSort)对象个数n。最多作最多作21VoidBubbleSort(int*data,intn){ i=0;while(i<n-1){ last=n-1; for(j=n-1;j>i;j--) If(data[j]<data[j-1]){交换数据；last=j;}i=last; }}i是无序集的下界VoidBubbleSort(int*data,i22算法分析最好:n-1次比较,移动为0最坏需要一个附加空间稳定算法分析最好:n-1次比较,移动为023快速排序基本思想：任选一个记录，以其关键字为“枢轴”，序列中比它小的移动到该记录之前，反之移动到它之后通过一趟排序将待排的记录分割成两个区域，一个区域中记录的关键字比另一个区域的关键字小（一次划分）然后左右两边分别处理直到排好快速排序基本思想：24快速排序划分:pivotpos=low;pivot=D[low];for(i=low+1;i<=high;i++) if(D[i].Key<=pivot.Key&&++pivotpos!=i) D[pivotpos]和D[i]交换;D[pivotpos]和D[low]交换;快速排序划分:25第7章-排序-Sorting第3章课件26第7章-排序-Sorting第3章课件27快速排序算法分析N个元素,排列有n!种,每个元素可以充当界点,界点的情况有n种平均时间复杂性:T(n)=cn+∑[T(k-1)+T(n-k)]/n,k=1:n设:T(0)=T(1)=b;T(n)=cn+2∑T(i)/n,i=0:n-1nT(n)=c(2n-1)+(n+1)T(n-1)T(n)<=2c(n+1)log(n+1)+b(n+1)/2快速排序算法分析N个元素,排列有n!种,每个元素可以充当界点28快速排序算法分析平均情况下,时间渐进复杂度是O(nlogn)，通常认为是在平均情况下的最佳排序.最坏情况:正序比较次数T(n)=(n-1)+(n-2)+…+1=n2/2,可以通过随机选择界点来避免将递归改为非递归快速排序算法分析平均情况下,时间渐进复杂度是O(nlogn)29快速排序算法分析空间最坏情况需要的栈O(n)可以通过先处理短的分段,来降低辅助空间到O(logn),当只有1个元素的时候不需要保存上下界,而非均匀分段时,下降的速度更快.不稳定对于n较大的平均情况而言,快速排序是“快速”的,但是当n很小时,这种排序方法往往比其它简单排序方法还要慢。快速排序算法分析空间最坏情况需要的栈O(n)30上机练习:P171:插入排序P221:快速排序上机练习:P171:插入排序31第7章排序(2)第7章排序(2)32回顾排序的基本概念排序算法的分析插入排序(直接,二分)交换排序(冒泡,快速)回顾排序的基本概念33第7章-排序-Sorting第3章课件34内容提要插入排序(直接,二分)交换(冒泡,快速)选择(selection,堆排序)归并(merge)基数排序内容提要插入排序(直接,二分)35选择排序N个元素,每次挑出最大或者最小,执行(n-1)次循环选择排序N个元素,每次挑出最大或者最小,执行(n-1)次循环36第7章-排序-Sorting第3章课件37直接选择排序的排序码比较次数KCN与整个待排序对象序列象的初始排列无关。移动次数:最好:0最坏:3(n-1)稳定直接选择排序的排序码比较次数KCN与整个待排序对象序列象的38堆排序树性选择排序堆的定义：n个元素的序列{k0，k1，……，kn-1}，当且仅当满足以下关系时，称之为堆最小化堆ki<=k2i+1ki<=k2i+2最大化堆Ki>=k2i+1ki>=k2i+2(i=0,1,2,……,(n-2)/2)最大化堆最大的结点一定出现在堆顶上。堆排序树性选择排序39归并排序归并，是将两个或两个以上的有序表合并成一个新的有序表。对象序列initList中两个有序表V[1]…V[m]和V[m+1]…V[n]。它们可归并成一个有序表,存于另一对象序列mergedList的V[1]…V[n]中。这种归并方法称为两路归并(2-waymerging)

归并排序归并，是将两个或两个以上的有序表合并成一个新的有序表40设变量i和j分别是表V[1]…V[m]和V[m+1]…V[n]的当前检测指针。变量k是存放指针。设变量i和j分别是表V[1]…V[m]和V[m+1]41迭代的归并排序算法

迭代的归并排序算法就是利用两路归并过程进行排序的。其基本思想是：假设初始序列有n个对象，首先把它看n个长度为1的有序子序列,两两并归,重复上述操作,直到得到一个序列.迭代的归并排序算法

迭代的归并排序算法就是利用两路归并过程进42算法分析辅助空间占用多稳定算法分析辅助空间占用多43递归的表归并排序

与快速排序类似，归并排序也可以利用划分为子序列的方法递归实现。在递归的归并排序方法中，首先要把整个待排序序列划分为两个长度大致相等的部分,左子表和右子表。对子表分别递归地进行排序,然后再把排好序的两个子表并归.递归的表归并排序

与快速排序类似，归并排序也可以利用划分为子44算法分析链表的归并排序方法的递归深度为O(log2n)，对象排序码的比较次数为O(nlog2n)。稳定算法分析链表的归并排序方法的递归深度为O(log2n)，对45基数排序不进行关键字的比较,而是利用”分配”和”收集”收集后的序列：2、52、5、7、17、18、9基数排序不进行关键字的比较,而是利用”分配”和”收集”46第7章-排序-Sorting第3章课件47空间：采用顺序分配，显然不合适。由于每个口袋都有可能存放所有的待排序的整数。所以，额外空间的需求为10n，太大了。采用链接分配是合理的。额外空间的需求为n，通常再增加指向每个口袋的首尾指针就可以了。在一般情况下，设每个键字的取值范围为d,首尾指针共计2×radix个，总的空间为O(n+2×radix)。时间：上例中每个数计有2位，因此执行2次分配和收集就可以了。在一般情况下，每个结点有d位关键字，必须执行d次分配和收集操作。 每次分配的代价：O(n) 每次收集的代价：O(radix) 总的代价为：O(d×(n+radix))空间：采用顺序分配，显然不合适。由于每个口袋都有可能存放所有48第7章-排序-Sorting第3章课件49voidRadixSort(staticlinklistlist,intd,intradix) {intrear[radix],front[radix]; for(i=0;i<list.Size;i++) list.Vector[i].link=i+1; list.Vector[CurrentSize].link=0; intcurrent=1;//最前面的结点下标为1,0号结点用作头结点 for(i=d-1;i>=0;i--){ for(intj=0;j<radix;j++)front[j]=0; while(current!=0) {intk=list.Vector[current].key[i]; if(front[k]==0)front[k]=current; elselist.Vextor[rear[k]].link=current; rear[k]=current; current=list.Vector[current].link;} j=0; while(front[j]==0)j++; list.Vector[0].link=current=front[j]; intlast=rear[j]; for(k=j+1;k<radix;k++) if(front[k]){list.Vector[last].link=front[k];last=rear[k];} list.Vector[last].link=0; }}//本程序并不十分严格，请大家作为算法来看。voidRadixSort(staticlinklistl50O(nlogn)O(n2)O(n)(基数排序)O(nlogn)O(n2)O(n)(基数排序)51排序算法选择待排序的个数记录本身的大小关键字的分布排序稳定性的要求排序算法选择待排序的个数52第7章排序Sorting[严陈]第3章第7章排序Sorting53内容提要排序的基本概念排序算法的分析插入排序(直接,二分)交换排序(冒泡,快速)选择(selection,堆排序)归并(merge)基数排序内容提要排序的基本概念54基本概念排序：将一组杂乱无章的数据按一定的规律顺次排列起来。数据表(datalist):它是待排序数据对象的有限集合。排序码(key):通常数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。基本概念排序：将一组杂乱无章的数据按一定的规律顺次排列起来。55分类内排序与外排序内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。分类内排序与外排序56排序算法的稳定性如果在对象序列中有两个对象r[i]和r[j],它们的排序码k[i]==k[j],

稳定的:排序前后,对象r[i]和r[j]的相对位置不变

不稳定:else排序算法的稳定性如果在对象序列中有两个对象r[i]和r[j]57算法评价时间开销:排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象排序码序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算空间开销：算法执行时所需的附加存储算法评价时间开销:58插入排序插入排序59第7章-排序-Sorting第3章课件60第7章-排序-Sorting第3章课件61直接插入排序直接插入排序62直接插入排序直接插入排序63直接插入排序:算法分析设待排序对象个数为n,则该算法的主程序执行n-1趟排序码比较次数和对象移动次数与对象排序码的初始排列有关最好情况下,排序前对象有序 比较(KCN):n-1;移动次数(RMN):为2(n-1)最坏情况下,第i趟时第i个对象必须与前面i个对象都做排序码比较,并且每做1次比较就要做1次数据移动。

直接插入排序:算法分析设待排序对象个数为n,则该算法的主程序64在平均情况下的排序码比较次数和对象移动次数约为n2/4。因此，直接插入排序的时间复杂度为o(n2)

直接插入排序是一种稳定的排序方法在平均情况下的排序码比较次数和对象移动次数约为n2/4。因此65二分插入排序(BinaryInsertsort)

基本思想是:设在顺序表中有一个对象序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已经排好序的对象。在插入V[i]时,利用二分搜索法寻找V[i]的插入位置。二分插入排序(BinaryInsertsort)基本思66二分插入排序二分插入排序67二分插入排序:分析二分搜索比顺序搜索查找快,所以二分插入排序就平均性能来说比直接插入排序要快。它所需的排序码比较次数与待排序对象序列的初始排列无关,仅依赖于对象个数。在插入第i个对象时,需要经过log2i+1次排序码比较,才能确定它应插入的位置。因此,将n个对象(为推导方便,设为n=2k)用折半插入排序所进行的排序码比较次数为二分插入排序是一个稳定的排序方法。二分插入排序:分析二分搜索比顺序搜索查找快,所以二分插入排序68当n较大时,总排序码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况要差。在对象的初始排列已经按排序码排好序或接近有序时,直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排序的对象移动次数与直接插入排序相同,依赖于对象的初始排列当n较大时,总排序码比较次数比直接插入排序的最坏情况要好得69使用链表插入排序每插入一个对象，最大排序码比较次数等于链表中已排好序的对象个数最小排序码比较次数为1

故总的排序码比较次数最小为(n-1)最大为移动次数为0空间增加了指针域,和头结点使用链表插入排序每插入一个对象，最大排序码比较次数等于链表70交换排序交换排序71交换排序数据两两比较，逆序交换，直到全部有序冒泡，快速交换排序数据两两比较，逆序交换，直到全部有序72冒泡排序(BubbleSort)对象个数n。最多作最多作n-1趟，i=1,2,…,n-1i趟中从后向前j=n-1,n-2,……,i，顺次两两比较比较如果发生逆序，则 交换V[j-1]和V[j]。冒泡排序(BubbleSort)对象个数n。最多作最多作73VoidBubbleSort(int*data,intn){ i=0;while(i<n-1){ last=n-1; for(j=n-1;j>i;j--) If(data[j]<data[j-1]){交换数据；last=j;}i=last; }}i是无序集的下界VoidBubbleSort(int*data,i74算法分析最好:n-1次比较,移动为0最坏需要一个附加空间稳定算法分析最好:n-1次比较,移动为075快速排序基本思想：任选一个记录，以其关键字为“枢轴”，序列中比它小的移动到该记录之前，反之移动到它之后通过一趟排序将待排的记录分割成两个区域，一个区域中记录的关键字比另一个区域的关键字小（一次划分）然后左右两边分别处理直到排好快速排序基本思想：76快速排序划分:pivotpos=low;pivot=D[low];for(i=low+1;i<=high;i++) if(D[i].Key<=pivot.Key&&++pivotpos!=i) D[pivotpos]和D[i]交换;D[pivotpos]和D[low]交换;快速排序划分:77第7章-排序-Sorting第3章课件78第7章-排序-Sorting第3章课件79快速排序算法分析N个元素,排列有n!种,每个元素可以充当界点,界点的情况有n种平均时间复杂性:T(n)=cn+∑[T(k-1)+T(n-k)]/n,k=1:n设:T(0)=T(1)=b;T(n)=cn+2∑T(i)/n,i=0:n-1nT(n)=c(2n-1)+(n+1)T(n-1)T(n)<=2c(n+1)log(n+1)+b(n+1)/2快速排序算法分析N个元素,排列有n!种,每个元素可以充当界点80快速排序算法分析平均情况下,时间渐进复杂度是O(nlogn)，通常认为是在平均情况下的最佳排序.最坏情况:正序比较次数T(n)=(n-1)+(n-2)+…+1=n2/2,可以通过随机选择界点来避免将递归改为非递归快速排序算法分析平均情况下,时间渐进复杂度是O(nlogn)81快速排序算法分析空间最坏情况需要的栈O(n)可以通过先处理短的分段,来降低辅助空间到O(logn),当只有1个元素的时候不需要保存上下界,而非均匀分段时,下降的速度更快.不稳定对于n较大的平均情况而言,快速排序是“快速”的,但是当n很小时,这种排序方法往往比其它简单排序方法还要慢。快速排序算法分析空间最坏情况需要的栈O(n)82上机练习:P171:插入排序P221:快速排序上机练习:P171:插入排序83第7章排序(2)第7章排序(2)84回顾排序的基本概念排序算法的分析插入排序(直接,二分)交换排序(冒泡,快速)回顾排序的基本概念85第7章-排序-Sorting第3章课件86内容提要插入排序(直接,二分)交换(冒泡,快速)选择(selection,堆排序)归并(merge)基数排序内容提要插入排序(直接,二分)87选择排序N个元素,每次挑出最大或者最小,执行(n-1)次循环选择排序N个元素,每次挑出最大或者最小,执行(n-1)次循环88第7章-排序-Sorting第3章课件89直接选择排序的排序码比较次数KCN与整个待排序对象序列象的初始排列无关。移动次数:最好:0最坏:3(n-1)稳定直接选择排序的排序码比较次数KCN与整个待排序对象序列象的90堆排序树性选择排序堆的定义：n个元素的序列{k0，k1，……，kn-1}，当且仅当满足以下关系时，称之为堆最小化堆ki<=k2i+1ki<=k2i+2最大化堆Ki>=k2i+1ki>=k2i+2(i=0,1,2,……,(n-2)/2)最大化堆最大的结点一定出现在堆顶上。堆排序树性选择排序91归并排序归并，是将两个或两个以上的有序表合并成一个新的有序表。对象序列initList中两个有序表V[1]…V[m]和V[m+1]…V[n]。它们可归并成一个有序表,存于另一对象序列mergedList的V[1]…V[n]中。这种归并方法称为两路归并(2-waymerging)

归并排序归并，是将两个或两个以上的有序表合并成一个新的有序表92设变量i和j分别是表V[1]…V[m]和V[m+1]…V[n]的当前检测指针。变量k是存放指针。设变量i和j分别是表V[1]…V[m]和V[m+1]93迭代的归并排序算法

迭代的归并排序算法就是利用两路归并过程进行排序的。其基本思想是：假设初始序列有n个对象，首先把它看n个长度为1的有序子序列,两两并归,重复上述操作,直到得到一个序列.迭代的归并排序算法

迭代的归并排序算法就是利用两路归并过程进94算法分析辅助空间占用多稳定算法分析辅助空间占用多95递归的表归并排序

与快速排序类似，归并排序也可以利用划分为子序列的方法递归实现。在递归的归并排序方法中，首先要把整个待排序序列划分为两个长度大致相等的部分,左子表和右子表。对子表分别递归地进行排序,然后再把排好序的两个子表并归.递归的表归并排序

与快速排序类似，归并排序也可以利用划分为子96算法分析链表的归并排序方法的递归深度为O(log2n)，对象排序码的比较次数为O(nlog2n)。稳定算法分析链表的归并排序方法的递归深度为O(log2n)，对97基数排序不进行关键字的比较,而是利用”分配”和”收集”收集后的序列：2、52、5、7、17、18、9基数排序不进行关键字的比较,而是利用”分配”和”收集”98第7章-排序-Sorting第3章课件99空间：采用顺序分配，显然不合适。由于每个口袋都有可能存放所有的待排序的整数。所以，额外空间的需求为10n，太大了。采用链接分配是合理的。额外空间的需求为n，通常再增加指向每个口袋的首尾指针就可以了。在一般情况下，设每个键字的取值范围为d,首尾指针共计2×r