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

1、第第7章章 排序排序Sorting严陈第3章内容提要内容提要l排序的基本概念l排序算法的分析l插入排序(直接,二分)l交换排序(冒泡,快速)l选择(selection,堆排序)l归并(merge)l基数排序基本概念基本概念l排序：将一组杂乱无章的数据按一定的规律顺次排列起来。l数据表(data list):它是待排序数据对象的有限集合。l排序码(key):通常数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。分类分类l内排序与外排序l内排序是指在排序期间数据对象全部存放在内存的排序；

2、l外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。排序算法的稳定性排序算法的稳定性l如果在对象序列中有两个对象ri和rj,它们的排序码ki=kj,稳定的:排序前后,对象ri和和r j的相对位置不的相对位置不变变不稳定:else算法评价算法评价l时间开销:l排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。l算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象排序码序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算 l空间开销：算法执行时所需的附加存储插入排序插入排序直接插入排序直接插入排

3、序直接插入排序直接插入排序直接插入排序直接插入排序:算法分析算法分析l设待排序对象个数为n,则该算法的主程序执行n-1趟排序码比较次数和对象移动次数与对象排序码的初始排列有关l最好情况下,排序前对象有序比较(KCN):n-1;移动次数(RMN):为2(n-1)l最坏情况下,第i趟时第i个对象必须与前面i个对象都做排序码比较,并且每做1次比较就要做1次数据移动。l在平均情况下的排序码比较次数和对象移动次数约为n2/4。因此，直接插入排序的时间复杂度为o(n2)l直接插入排序是一种稳定的排序方法 二分插入排序二分插入排序(Binary Insert sort)l基本思想是:设在顺序表中有一个对象序

4、列V0,V1,V n-1。其中,V0,V 1,Vi-1是已经排好序的对象。在插入Vi时,利用二分搜索法寻找Vi的插入位置。二分插入排序二分插入排序二分插入排序二分插入排序:分析分析l二分搜索比顺序搜索查找快,所以二分插入排序就平均性能来说比直接插入排序要快。l它所需的排序码比较次数与待排序对象序列的初始排列无关,仅依赖于对象个数。在插入第i个对象时,需要经过log2 i+1次排序码比较,才能确定它应插入的位置。因此,将n个对象(为推导方便,设为n=2 k)用折半插入排序所进行的排序码比较次数为l二分插入排序是一个稳定的排序方法。l 当n较大时,总排序码比较次数比直接插入排序的最坏情况要好得多,

5、但比其最好情况要差。l在对象的初始排列已经按排序码排好序或接近有序时,直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排序的对象移动次数与直接插入排序相同,依赖于对象的初始排列 使用链表插入排序使用链表插入排序 l每插入一个对象，最大排序码比较次数等于链表中已排好序的对象个数 l最小排序码比较次数为1 l故总的排序码l比较次数最小为(n-1)l最大为l 移动次数为0l空间增加了指针域,和头结点交换排序交换排序交换排序交换排序l数据两两比较，逆序交换，直到全部有序l冒泡，快速冒泡排序冒泡排序(Bubble Sort)l对象个数n。最多作最多作n-1趟，i=1,2,n-1li趟中从后向

6、前j=n-1,n-2,i，顺次两两比较l比较如果发生逆序，则交换V j-1 和V j。lVoid BubbleSort(int*data,int n)i=0;while(ii;j-)If(datajdataj-1)交换数据；last=j;i=last;i是无序集的下界算法分析算法分析l最好:n-1次比较,移动为0l最坏l需要一个附加空间l稳定快速排序快速排序l基本思想：l任选一个记录，以其关键字为“枢轴”，序列中比它小的移动到该记录之前，反之移动到它之后l通过一趟排序将待排的记录分割成两个区域，一个区域中记录的关键字比另一个区域的关键字小（一次划分）l然后左右两边分别处理直到排好快速排序快速排

7、序划分划分:pivotpos=low;pivot=Dlow;for(i=low+1;i=high;i+)if(D i.Key=pivot.Key&+pivotpos!=i)D pivotpos 和D i交换;D pivotpos 和D low 交换;快速排序算法分析快速排序算法分析lN个元素,排列有n!种,每个元素可以充当界点,界点的情况有n种l平均时间复杂性:T(n)=cn+T(k-1)+T(n-k)/n,k=1:n 设:T(0)=T(1)=b;T(n)=cn+2T(i)/n,i=0:n-1 nT(n)=c(2n-1)+(n+1)T(n-1)T(n)=2c(n+1)log(n+1)+b(n+

8、1)/2快速排序算法分析快速排序算法分析l平均情况下平均情况下,时间渐进复杂度是时间渐进复杂度是O(nlogn)，通常认为是在平均情况下的最佳排序.l最坏情况:正序 比较次数T(n)=(n-1)+(n-2)+1=n2/2,l可以通过随机选择界点来避免l将递归改为非递归快速排序算法分析快速排序算法分析l空间最坏情况需要的栈O(n)l可以通过先处理短的分段,来降低辅助空间到O(logn),当只有1个元素的时候不需要保存上下界,而非均匀分段时,下降的速度更快.l不稳定l对于n较大的平均情况而言,快速排序是“快速”的,但是当n很小时,这种排序方法往往比其它简单排序方法还要慢。上机练习上机练习:lP17

9、1:插入排序lP221:快速排序第第7章章 排序排序(2)回顾回顾l排序的基本概念l排序算法的分析l插入排序(直接,二分)l交换排序(冒泡,快速)内容提要内容提要l插入排序(直接,二分)l交换(冒泡,快速)l选择(selection,堆排序)l归并(merge)l基数排序选择排序选择排序lN个元素,每次挑出最大或者最小,执行(n-1)次循环l直接选择排序的排序码比较次数KCN 与整个待排序对象序列象的初始排列无关。l移动次数:l最好:0l最坏:3(n-1)l稳定堆排序堆排序l树性选择排序l堆的定义：n 个元素的序列 k0，k1，kn-1，当且仅当满足以下关系时，称之为堆l最小化堆ki=k2i+

10、1 ki=k2i+1 ki=k2i+2(i=0,1,2,(n-2)/2)l最大化堆最大的结点一定出现在堆顶上。归并排序归并排序l归并，是将两个或两个以上的有序表合并成一个新的有序表。l 对象序列initList中两个有序表V1 V m和V m+1 V n。它们可归并成一个有序表,存于另一对象序列mergedList的V1 V n中。l这种归并方法称为两路归并(2-way merging)l设变量i和j分别是表V1 V m和V m+1 V n的当前检测指针。变量k是存放指针。迭代的归并排序算法迭代的归并排序算法l迭代的归并排序算法就是利用两路归并过程进行排序的。其基本思想是：l 假设初始序列有n

11、个对象，首先把它看n个长度为1的有序子序列,两两并归,重复上述操作,直到得到一个序列.算法分析算法分析l辅助空间占用多l稳定递归的表归并排序递归的表归并排序l与快速排序类似，归并排序也可以利用划分为子序列的方法递归实现。l在递归的归并排序方法中，首先要把整个待排序序列划分为两个长度大致相等的部分,左子表和右子表。对子表分别递归地进行排序,然后再把排好序的两个子表并归.算法分析算法分析l链表的归并排序方法的递归深度为O(log2 n)，对象排序码的比较次数为O(n log2 n)。l稳定基数排序基数排序l不进行关键字的比较,而是利用”分配”和”收集”收集后的序列：2、52、5、7、17、18、9

12、l空间：采用顺序分配，显然不合适。由于每个口袋都有可能存放所有的待排序的整数。所以，额外空间的需求为10n，太大了。采用链接分配是合理的。额外空间的需求为n，通常再增加指向每个口袋的首尾指针就可以了。在一般情况下，设每个键字的取值范围为d,首尾指针共计2radix 个，总的空间为O(n+2radix)。l时间：上例中每个数计有2 位，因此执行2 次分配和收集就可以了。在一般情况下，每个结点有d 位关键字，必须执行d 次分配和收集操作。每次分配的代价：O(n)每次收集的代价：O(radix)总的代价为：O(d(n+radix)lvoidRadixSort(staticlinklist list,

13、int d,int radix)int rear radix,front radix;for(i=0;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;else list.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;int last=rear j;for(k=j+1;k radix;k+)if(front k )list.Vector last.link=front k;last=reark;list.Vector last.link=0;/本程序并不十分严格，请大家作为算法来看。lO(nlog n)O(n2)O(n)(基数排序)排序算法选择排序算法选择l待排序的个数l记录本身的大小l关键字的分布l排序稳定性的要求