数据结构(严蔚敏)课件第10章

2020年9月15日星期二第1页第十章排序2020年9月15日星期二第2页【课前思考】1.你熟悉排序吗？你过去曾经学过哪些排序方法？在第一章中曾以选择排序和起泡排序为例讨论算法实践复杂度，不知你还记得吗？2.你自己有没有编过排序的程序？是用的什么策略？2020年9月15日星期二第3页【学习目标】1．理解排序的定义和各种排序方法的特点，并能加以灵活应用。排序方法有不同的分类方法，基于关键字间的比较进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。2．掌握各种排序方法的时间复杂度的分析方法。能从关键字间的比较次数分析排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可分为三类：O(n2)的简单排序方法，O(n·logn)的高效排序方法和O(d·n)的基数排序方法。3．理解排序方法稳定或不稳定的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。2020年9月15日星期二第4页【重点和难点】希尔排序、快速排序、堆排序和归并排序等高效方法是本章的学习重点和难点。【知识点】排序、直接插入排序、折半插入排序、表插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序、基数排序、排序方法的综合比较。2020年9月15日星期二第5页【学习指南】本章学习的要点主要是了解各种排序方法实现时所依据的原则以及它们的主要操作（“关键字间的比较”和“记录的移动”）的时间分析。学习中应注意掌握各种排序方法实现的要点，可通过对基础知识题中算法的手工执行和比较分析，切实掌握各种排序过程的排序特点所在，注意同一排序方法在不同的教科书上可以有不同书写形式描述的算法。在学习本章过程中需练习的算法设计题为：10.23，10.25，10.27，10.32，10.34，10.38,10.42和10.45。2020年9月15日星期二第6页10.1概述10.2插入排序10.3快速排序10.4堆排序10.5归并排序10.6基数排序10.7各种排序方法的综合比较10.8外部排序2020年9月15日星期二第7页10.1概述一、排序的定义二、内部排序和外部排序三、内部排序方法的分类2020年9月15日星期二第8页一、什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,972020年9月15日星期二第9页一般情况下，假设含n个记录的序列为{R1,R2,…，Rn}其相应的关键字序列为{K1,K2,…，Kn}这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：Kp1≤Kp2≤…≤Kpn按此固有关系将上式记录序列重新排列为{Rp1,Rp2,…，Rpn}的操作称作排序。2020年9月15日星期二第10页二、内部排序和外部排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。2020年9月15日星期二第11页三、内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区2020年9月15日星期二第12页基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：插入类交换类选择类归并类其它方法2020年9月15日星期二第13页待排记录的数据类型定义如下:#defineMAXSIZE1000//待排顺序表最大长度typedefintKeyType;//关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其它数据项}RcdType;//记录类型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]闲置intlength;//顺序表长度}SqList;//顺序表类型2020年9月15日星期二第14页1.插入类将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。2020年9月15日星期二第15页2.交换类通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。2020年9月15日星期二第16页3.选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。2020年9月15日星期二第17页4.归并类通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。5.其它方法2020年9月15日星期二第18页10.2插入排序2020年9月15日星期二第19页有序序列R[1..i-1]R[i]无序序列R[i..n]一趟直接插入排序的基本思想：有序序列R[1..i]无序序列R[i+1..n]2020年9月15日星期二第20页实现“一趟插入排序”可分三步进行：3．将R[i]插入(复制)到R[j+1]的位置上。2．将R[j+1..i-1]中的所有记录均后移一个位置；1．在R[1..i-1]中查找R[i]的插入位置，R[1..j].keyR[i].keyR[j+1..i-1].key；2020年9月15日星期二第21页直接插入排序（基于顺序查找）表插入排序（基于链表存储）不同的具体实现方法导致不同的算法描述折半插入排序（基于折半查找）希尔排序（基于逐趟缩小增量）2020年9月15日星期二第22页一、直接插入排序利用“顺序查找”实现“在R[1..i-1]中查找R[i]的插入位置”算法的实现要点：2020年9月15日星期二第23页从R[i-1]起向前进行顺序查找，监视哨设置在R[0]；R[0]=R[i];//设置“哨兵”循环结束表明R[i]的插入位置为j+1R[0]jR[i]for(j=i-1;R[0].keyR[j].key;--j);//从后往前找j=i-1插入位置2020年9月15日星期二第24页对于在查找过程中找到的那些关键字不小于R[i].key的记录，并在查找的同时实现记录向后移动；for(j=i-1;R[0].keyR[j].key;--j);R[j+1]=R[j]R[0]jR[i]j=i-1上述循环结束后可以直接进行“插入”插入位置2020年9月15日星期二第25页令i=2，3，…,n,实现整个序列的排序。for(i=2;i=n;++i)if(R[i].keyR[i-1].key){在R[1..i-1]中查找R[i]的插入位置;插入R[i];}2020年9月15日星期二第26页voidInsertionSort(SqList&L){//对顺序表L作直接插入排序。for(i=2;i=L.length;++i)if(L.r[i].keyL.r[i-1].key){}}//InsertSortL.r[0]=L.r[i];//复制为监视哨for(j=i-1;L.r[0].keyL.r[j].key;--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置2020年9月15日星期二第27页内部排序的时间分析：实现内部排序的基本操作有两个：（2）“移动”记录。（1）“比较”序列中两个关键字的大小；2020年9月15日星期二第28页对于直接插入排序：最好的情况（关键字在记录序列中顺序有序）：“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：“比较”的次数：112nni02)1)(4()1(2nnini“移动”的次数：“移动”的次数：2)1)(4()1(2nnini2020年9月15日星期二第29页因为R[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。二、折半插入排序2020年9月15日星期二第30页voidBiInsertionSort(SqList&L){}//BInsertSort在L.r[1..i-1]中折半查找插入位置；for(i=2;i=L.length;++i){}//forL.r[0]=L.r[i];//将L.r[i]暂存到L.r[0]for(j=i-1;j=high+1;--j)L.r[j+1]=L.r[j];//记录后移L.r[high+1]=L.r[0];//插入2020年9月15日星期二第31页low=1;high=i-1;while(low=high){}m=(low+high)/2;//折半if(L.r[0].keyL.r[m].key)high=m-1;//插入点在低半区elselow=m+1;//插入点在高半区2020年9月15日星期二第32页14364952805861239775ilowhighmmlowlowmhigh14364952586180239775ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r2020年9月15日星期二第33页三、表插入排序为了减少在排序过程中进行的“移动”记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。2020年9月15日星期二第34页voidLInsertionSort(ElemSL[]，intn){//对记录序列SL[1..n]作表插入排序SL[0].key=MAXINT;SL[0].next=1;SL[1].next=0;for(i=2;i=n;++i)for(j=0,k=SL[0].next;SL[k].key=SL[i].key;j=k,k=SL[k].next){SL[j].next=i;SL[i].next=k;}//结点i插入在结点j和结点k之间}//LinsertionSort2020年9月15日星期二第35页算法中使用了三个指针：其中：p指示第i个记录的当前位置i指示第i个记录应在的位置q指示第i+1个记录的当前位置如何在排序之后调整记录序列？2020年9月15日星期二第36页voidArrange(ElemSL[],intn){p=SL[0].next;//p指示第一个记录的当前位置for(i=1;in;++i){while(pi)p=SL[p].next;q=SL[p].next;//q指示尚未调整的表尾if(p!=i){SL[p]←→SL[i];//交换记录，使第i个记录到位SL[i].next=p;//指向被移走的记录}p=q;//p指示尚未调整的表尾，//为找第i+1个记录作准备}}//Arrange2020年9月15日星期二第37页四、希尔排序（又称缩小增量排序）基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是，“跳跃式”的插入排序。具体做法为：2020年9月15日星期二第38页将记录序列分成若干子序列，分别对每个子序列进行插入排序。其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。例如：将n个记录分成d个子序列：{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}2020年9月15日星期二第39页例如：162512304711233691831第一趟希尔排序，设增量d=5112312918162536304731第二趟希尔排序，设增量d=3918121123162531304736第三趟希尔排序，设增量d=19111216182325303136472020年9月15日星期二第40页v