第9章-排序案例优秀PPT.ppt

第九章第九章排序排序10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 堆排序堆排序10.5 归并排序归并排序10.6 各种排序方法的综合比较各种排序方法的综合比较10.1 概概 述述一、排序的定义一、排序的定义二、内部排序和外部排序二、内部排序和外部排序三、内部排序方法的分类三、内部排序方法的分类一、什么是排序？一、什么是排序？排序是计算机内常常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,97 一般状况下，假设含n个记录的序列为 R1,R2,，Rn 其相应的关键字序列为 K1,K2,，Kn 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：Kp1Kp2Kpn按此固有关系将上式记录序列重新排列为 Rp1,Rp2,，Rpn 的操作操作称作排序排序。二、内部排序和外部排序二、内部排序和外部排序若整个排序过程不须要访问外存便能完成，则称此类排序问题为内部排序；反之，若参与排序的记录数量很大，整个序列的排序过程不行能在内存中 完成，则称此类排序问题为外部排序。三、内部排序的方法三、内部排序的方法内部排序的过程是一个逐步扩大逐步扩大记录的有序序列长度有序序列长度的过程。经过一趟排序经过一趟排序有序序列区无 序 序 列 区有序序列区无 序 序 列 区基于不同的“扩大扩大”有序序列长度的方法，内部排序方法方法，内部排序方法大致可分下列几种类型：插入类插入类交换类交换类选择类选择类 归并类归并类待排记录的数据类型定义如下待排记录的数据类型定义如下:#define MAXSIZE 1000/待排依次表最大长度待排依次表最大长度typedef int KeyType;/关键字类型为整数类型关键字类型为整数类型typedef struct KeyType key;/关键字项关键字项 InfoType otherinfo;/其它数据项其它数据项 RcdType;/记录类型记录类型typedef struct RcdType rMAXSIZE+1;/r0闲置闲置 int length;/依次表长度依次表长度 SqList;/依次表类型依次表类型 10.2 插插 入入 排排 序序有序序列R1.i-1Ri无序序列 Ri.n一趟干脆插入排序的基本思想：有序序列R1.i无序序列 Ri+1.n实现实现“一趟插入排序一趟插入排序”可分三步进行：可分三步进行：3将Ri 插入插入(复制)到Rj+1的位置上。2将将Rj+1.i-1中的全部记录均后移中的全部记录均后移 一个位置；一个位置；1在R1.i-1中查找查找Ri的插入位置，R1.j.key Ri.key Rj+1.i-1.key；干脆插入排序（基于依次干脆插入排序（基于依次查找）查找）希尔排序希尔排序（基于逐趟缩小增量）（基于逐趟缩小增量）不同的具体实现方法导致不同的算法描述不同的具体实现方法导致不同的算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）一、干脆插入排序一、干脆插入排序利用“依次查找”实现“在R1.i-1中查找Ri的插入位置”算法的实现要点：算法的实现要点：对于在查找过程中找到的那些关键字不小于Ri.key的记录，并在查找的同时实现记录向后移动；for(j=i-1;R0.keyRj.key;-j);Rj+1=RjR0jRij=i-1上述循环结束后可以干脆进行“插入”插入位置插入位置令 i=2，3，,n,实现整个序列的排序。for(i=2;i=n;+i)if(Ri.keyRi-1.key)在 R1.i-1中查找Ri的插入位置;插入Ri;初始关键字序列：【初始关键字序列：【1313】，】，6 6，3 3，3131，9 9，2727，5 5，11 11第一次排序：第一次排序：【6,136,13】,3,31,9,27,5,11,3,31,9,27,5,11其次次排序：其次次排序：【3,6,133,6,13】,31,9,27,5,11,31,9,27,5,11第三次排序：第三次排序：【3,6,133,6,13，3131】,9,27,5,11,9,27,5,11第四次排序：第四次排序：【3,6,9,133,6,9,13，3131】,27,5,11,27,5,11第五次排序：第五次排序：【3,6,9,133,6,9,13，27,3127,31】,5,11,5,11第六次排序：第六次排序：【3,5,6,9,133,5,6,9,13，27,3127,31】,11,11第七次排序：第七次排序：【3,5,6,9,113,5,6,9,11，1313，27,3127,31】例：关键字序列例：关键字序列T=T=（1313，6 6，3 3，3131，9 9，2727，5 5，1111），请写出干脆插入排序的中间过程序列。），请写出干脆插入排序的中间过程序列。注：方括号注：方括号 【】中为已排序记录的关键字，下划横线的中为已排序记录的关键字，下划横线的 关键字关键字表示它对应的记录后移一个位置。表示它对应的记录后移一个位置。void InsertionSort(SqList&L)/对依次表对依次表 L 作干脆插入排序。作干脆插入排序。for(i=2;i=L.length;+i)if(L.ri.key L.ri-1.key)/InsertSortL.r0=L.ri;/复制为监视哨for(j=i-1;L.r0.key L.rj.key;-j)L.rj+1=L.rj;/记录后移L.rj+1=L.r0;/插入到正确位置内部排序的时间分析时间分析：实现内部排序的基本操作基本操作有两个：（2）“移动移动”记录。（1）“比较比较”序列中两个关键字的 大小；对于干脆插入排序：最好的状况（关键字在记录序列中依次有序）：最好的状况（关键字在记录序列中依次有序）：“比较”的次数：最坏的状况（关键字在记录序列中逆序有序）：最坏的状况（关键字在记录序列中逆序有序）：“比较”的次数：0“移动”的次数：“移动”的次数：时间效率：因为在最坏状况下，全部元素的比较次数总和为（01n-1)O(n2)。其他状况下也要考虑移动元素的次数。故时间困难度为O(n2)空间效率：仅占用1个缓冲单元O（1）算法的稳定性：稳定 因为 R1.i-1 是一个按关键字有序的有序序列，则可以利用折半查找折半查找实现“在R1.i-1中查找查找Ri的插入位置”，如此实现的插入排序为折半插折半插入入排序。二、折半插入排序二、折半插入排序void BiInsertionSort(SqList&L)/BInsertSort在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；for(i=2;i=high+1;-j)L.rj+1=L.rj;/记录后移L.rhigh+1=L.r0;/插入low=1;high=i-1;while(low=high)m=(low+high)/2;/折半if(L.r0.key L.rm.key)high=m-1;/插入点在低半区else low=m+1;/插入点在高半区14 36 49 52 80 58 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r 三、希尔排序（又称缩小增量排序）三、希尔排序（又称缩小增量排序）基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是，“跳动式”的插入排序。具体做法为：将记录序列分成若干子序列，分别对每个子序列进行插入排序。其中，d 称为增量，它的值在排序过程中从大到小渐渐缩小，直至最终一趟排序减为 1。例如：将 n 个记录分成 d 个子序列：R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 例如：16 25 12 30 47 11 23 36 9 18 31 第一趟希尔排序，设增量 d=511 23 12 9 18 16 25 36 30 47 31 其次趟希尔排序，设增量 d=39 18 12 11 23 16 25 31 30 47 36第三趟希尔排序，设增量 d=1 9 11 12 16 18 23 25 30 31 36 47 void ShellInsert(SqList&L,int dk)for(i=dk+1;i=n;+i)if(L.ri.key0&(L.r0.keyL.rj.key);j-=dk)L.rj+dk=L.rj;/记录后移，查找插入位置 L.rj+dk=L.r0;/插入 /if/ShellInsertvoid ShellSort(SqList&L,int dlta,int t)/增量为dlta的希尔排序 for(k=0;k1)/while/BubbleSorti=n;i=lastExchangeIndex;/本趟进行过交换的 /最终一个记录的位置 if(Rj+1.key Rj.key)Swap(Rj,Rj+1);lastExchangeIndex=j;/登记进行交换的记录位置 /iffor(j=1;j i;j+)lastExchangeIndex=1;留意留意:2.一般状况下，每经过一趟“起泡”，“i 减一”，但并不是每趟都如此。例如例如:25531579 89i=7i=6for(j=1;j i;j+)if(Rj+1.key Rj.key)13i=21.起泡排序的结束条件为，最终一趟没有进行“交换记录”。时间分析时间分析:最好的状况（关键字在记录序列中依次有序）：最好的状况（关键字在记录序列中依次有序）：只需进行一趟起泡只需进行一趟起泡“比较比较”的次数：的次数：最坏的状况（关键字在记录序列中逆序有序）：最坏的状况（关键字在记录序列中逆序有序）：需进行需进行n-1趟起泡趟起泡“比较比较”的次数：的次数：0“移动移动”的次数：的次数：“移动移动”的次数：的次数：n-1二、一趟快速排序（一次划分）二、一趟快速排序（一次划分）目标：目标：找一个记录，以它的关键字作为“枢轴枢轴”，凡其关键字小于枢轴关键字小于枢轴的记录均移动至该记录之前移动至该记录之前，反之，凡关键字大于关键字大于枢轴枢轴的记录均移动至该记录之后移动至该记录之后。致使一趟排序一趟排序之后，记录的无序序列Rs.t将分割成两部分分割成两部分：Rs.i-1和Ri+1.t，且 Rj.key Ri.key Rj.key (sji-1)枢轴枢轴 (i+1jt)。stlowhigh设设 Rs=52 为枢轴为枢轴 将 Rhigh.key 和 枢轴的关键字进行比较，要求Rhigh.key 枢轴的关键字 将 Rlow.key 和 枢轴的关键字进行比较，要求Rlow.key 枢轴的关键字high23low80high14low52例如例如R052lowhighhighhighlow 可见，经过“一次划分一次划分”，将关键字序列 52,49,80,36,14,58,61,97,23,75 调整为:23,49,14,36,(52)58,61,97,80,75 在调整过程中，设立了两个指针：low 和high，它们的初值分别为：s 和 t，之后渐渐减小 high，增加 low，并保证 Rhigh.key52，和 Rlow.key52,否则进行记录的“交换”。int Partition(RedType R,int low,int high)/Partition R0=Rlow;pivotkey=Rlow.key;/枢轴 while(lowhigh)while(low=pivotkey)-high;/从右向左搜寻从右向左搜寻Rlow=Rhigh;while(lowhigh&Rlow.key=pivotkey)+low;/从左向右搜寻从左向右搜寻Rhigh=Rlow;Rlow=R0;return low;三、快速排序三、快速排序 首先对无序的记录序列进行“一次划分一次划分”，之后分别分别对分割所得两个子序列“递归递归”进行快速排序进行快速排序。无 序 的 记 录 序 列无序记录子序列(1)无序子序列(2)枢轴枢轴一次划分分别进行快速排序void QSort(RedType&R,int s,int t)/对记录序列Rs.t进行快速排序 if(s t-1)/长度大于1 /QSortpivotloc=Partition(R,s,t);/对 Rs.t 进行一次划分一次划分QSort(R,s,pivotloc-1);/对低子序列递归排序，pivotloc是枢轴位置是枢轴位置QSort(R,pivotloc+1,t);/对高子序列递归排序void QuickSort(SqList&L)/对依次表进行快速排序对依次表进行快速排序 QSort(L.r,1,L.length);/QuickSort 第一次调用函数 Qsort 时，待排序记录序列的上、下界分别为 1 和 L.length。四、快速排序的时间分析四、快速排序的时间分析时间效率：O(nlog2n)因为每趟确定的元素呈指数增加空间效率：O（log2n）因为递归要用栈(存每层low，high和pivot)稳 定 性：不稳定 因为有跳动式交换。若待排记录的初始状态为按关键字有序若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间时，快速排序将蜕化为起泡排序，其时间困难度为困难度为O(n2)。为避开出现这种状况，需在进行一次划分之前，进行“予处理”，即：先对 R(s).key,R(t).key 和 R(s+t)/2.key，进行相互比较，然后取取关键字为 “三者之中三者之中”的记录为枢轴为枢轴记录。10.4 堆堆 排排 序序简简 单单 选选 择择 排排 序序堆堆 排排 序序一、简洁选择排序一、简洁选择排序假设排序过程中，待排记录序列的状态为：有序序列R1.i-1无序序列 Ri.n 第 i 趟简洁选择排序从中选出关键字最小的记录有序序列R1.i无序序列 Ri+1.n例：关键字序列例：关键字序列T=T=（2121，2525，4949，25*25*，1616，0808），请给出简洁选择排序的具体实现过程。），请给出简洁选择排序的具体实现过程。原始序列：原始序列：21，25，49，25*，16，08第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟08，25，49，25*，16，2108，16,49，25*，25，2108，16,21，25*，25，4908，16,21，25*，25，4908，16,21，25*，25，49简洁选择排序的算法描述如下：void SelectSort(Elem R,int n)/对记录序列对记录序列R1.n作简洁选择排序。作简洁选择排序。for(i=1;in;+i)/选择第选择第 i 小的记录，并交换到位小的记录，并交换到位 /SelectSortj=SelectMinKey(R,i);/在 Ri.n 中选择关键字最小的记录if(i!=j)RiRj;/与第 i 个记录交换时间性能分析时间性能分析时间效率：时间效率：O(n2)虽移动次数较少，虽移动次数较少，但比较次数仍多。但比较次数仍多。空间效率空间效率：O（1）没有附加单元没有附加单元（仅用到（仅用到1个个temp)算法的稳定性：算法的稳定性：不稳定不稳定10.5 归归 并并 排排 序序归并排序的过程基于下列基本思想基本思想进行：将两个或两个以上的有序子序列“归并”为一个有序序列。在内部排序中，通常接受的是2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个一个记录的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序子序列 Rl.m有序子序列有序子序列 Rm+1.n这个操作对依次表而言，是轻而易举的。void Merge(RcdType SR,RcdType&TR,int i,int m,int n)/将有序的记录序列 SRi.m 和 SRm+1.n /归并为有序的记录序列 TRi.n/Mergefor(j=m+1,k=i;i=m&j=n;+k)/将SR中记录由小到大地并入TR if(SRi.key=SRj.key)TRk=SRi+;else TRk=SRj+;if(i=m)TRk.n=SRi.m;/将剩余的 SRi.m 复制到 TRif(j=n)TRk.n=SRj.n;/将剩余的 SRj.n 复制到 TR归并排序的算法归并排序的算法假如记录无序序列 Rs.t 的两部分 Rs.(s+t)/2 和 R(s+t)/2+1.t分别按关键字有序，则利用上述归并算法很简洁将它们归并成整个记录序列是一个有序序列。由此，应当先分别对这两部分进行 2-路归并排序。例如：例如：52,23,80,36,68,14 (s=1,t=6)52,23,80 36,68,14 52,2380 52 23,52 23,52,8036,6814366836,6814,36,68 14,23,36,52,68,80 23void Msort(RcdType SR,RcdType&TR1,int s,int t)/将SRs.t 归并排序为 TR1s.t if(s=t)TR1s=SRs;else /Msort m=(s+t)/2;/将SRs.t平分为SRs.m和SRm+1.tMsort(SR,TR2,s,m);/递归地将SRs.m归并为有序的TR2s.mMsort(SR,TR2,m+1,t);/递归地SRm+1.t归并为有序的TR2m+1.tMerge(TR2,TR1,s,m,t);/将TR2s.m和TR2m+1.t归并到TR1s.tvoid MergeSort(SqList&L)/对依次表对依次表 L 作作2-路归并排序路归并排序 MSort(L.r,L.r,1,L.length);/MergeSort二路归并排序算法分析：二路归并排序算法分析：时间效率：时间效率：时间效率：时间效率：O(O(n nloglog2 2n n)因为在递归的归并排序算法中，函数因为在递归的归并排序算法中，函数Merge()做一做一趟两路归并排序，须要调用趟两路归并排序，须要调用merge()函数函数 n/(2len)O(n/len)次，而每次次，而每次merge()要执行比较要执行比较O(len)次，次，另外整个归并过程有另外整个归并过程有 log2n “层层”，所以算法总，所以算法总的时间困难度为的时间困难度为O(nlog2n)。空间效率：空间效率：O(n)因为须要一个与原始序列同样大小的协助序列。这因为须要一个与原始序列同样大小的协助序列。这正是此算法的缺点。正是此算法的缺点。稳定性：稳定稳定性：稳定10.6 各种排序方法的综合比较各种排序方法的综合比较一、时间性能一、时间性能1.平均的时间性能平均的时间性能基数排序基数排序时间困难度为时间困难度为 O(nlog2n)：快速排序、堆排序和归并排序快速排序、堆排序和归并排序时间困难度为时间困难度为 O(n2)O(n2)：干脆插入排序、起泡排序和干脆插入排序、起泡排序和简洁选择排序简洁选择排序时间困难度为时间困难度为 O(n):2.当待排记录序列按关键字依次有序时当待排记录序列按关键字依次有序时3.简洁选择排序、堆排序和归并排序的简洁选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布时间性能不随记录序列中关键字的分布而变更。而变更。干脆插入排序和起泡排序能达到O(n)的时间困难度，快速排序的时间性能蜕化为O(n2)。二、空间性能二、空间性能指的是排序过程中所需的协助空间大小1.全部的简洁排序方法全部的简洁排序方法(包括：干脆插包括：干脆插入、起泡和简洁选择入、起泡和简洁选择)和堆排序的空和堆排序的空间困难度为间困难度为O(1)；2.快速排序为快速排序为O(log2n)，为递归程序，为递归程序执行过程中，栈所需的协助空间；执行过程中，栈所需的协助空间；3.归并排序所需协助空间最多，其空归并排序所需协助空间最多，其空间困难度为间困难度为 O(n);4.链式基数排序需附设队列首尾指链式基数排序需附设队列首尾指针，则空间困难度为针，则空间困难度为 O(rd)。三、排序方法的稳定性能三、排序方法的稳定性能 1.稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有变更。2.当对多关键字的记录序列进行当对多关键字的记录序列进行LSD方法排序时，必需接受稳定的排序方方法排序时，必需接受稳定的排序方法。法。排序之前:Ri(K)Rj(K)排序之后:Ri(K)Rj(K)例如：例如：排序前(56,34,47,23,66,18,82,47)若排序后得到结果 (18,23,34,47,47,56,66,82)则称该排序方法是稳定稳定的;若排序后得到结果 (18,23,34,47,47,56,66,82)则称该排序方法是不稳定不稳定的。3.对于不稳定的排序方法，只要能举出一个实例说明即可。4.快速排序、堆排序和希尔排序是不稳快速排序、堆排序和希尔排序是不稳定的排序方法定的排序方法。例如例如:对 4,3,4,2 进行快速排序，得到 2,3,4,4 1.了解排序的定义和各种排序方法的了解排序的定义和各种排序方法的特点。熟悉各种方法的排序过程及其依特点。熟悉各种方法的排序过程及其依据的原则。基于据的原则。基于“关键字间的比较关键字间的比较”进行进行排序的方法可以按排序过程所依据的不排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。排序、归并排序和计数排序等五类。2.驾驭各种排序方法的时间困难驾驭各种排序方法的时间困难度的分析方法。能从度的分析方法。能从“关键字间的关键字间的比较次数比较次数”分析排序算法的平均状分析排序算法的平均状况和最坏状况的时间性能。况和最坏状况的时间性能。按平均时间困难度划分，内部排序可分为三类：O(n2)的简洁排序方法，O(nlogn)的高效排序方法 和 O(dn)的基数排序方法。3理解排序方法理解排序方法“稳定稳定”或或“不稳定不稳定”的的含义，弄清晰在什么状况下要求应用的含义，弄清晰在什么状况下要求应用的排序方法必需是稳定的。排序方法必需是稳定的。练习：若初始记录基本有序，则选用哪些排序方法比较适合？若初始记录基本无序，则最好选用哪些排序方法？请说明理由（排序方法各列举两种即可）。基本有序时可选用干脆插入、简洁选择、堆排序、冒泡排序、归并排序、(希尔排序)等方法，其中插入排序和冒泡应当是最快的。因为只有比较动作，无需移动元素。此时平均时间困难度为O(n)；无序的状况下最好选用快速排序、希尔排序、简洁选择排序等，这些算法的共同特点是，通过“振荡”让数值相差不大但位置差异很大的元素尽快到位。人有了学问，就会具备各种分析实力，明辨是非的实力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富学问，培育逻辑思维实力；通过阅读文学作品，我们能提高文学鉴赏水平，培育文学情趣；通过阅读报刊，我们能增长见识，扩大自己的学问面。有很多书籍还能培育我们的道德情操，给我们巨大的精神力气，鼓舞我们前进。