中国计量学院数据结构第10章-排序辩析优秀PPT.ppt

第十章 内部排序10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 选择排序选择排序10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种排序方法的综合比较各种排序方法的综合比较10.1 概概 述述一、何为排序一、何为排序二、内部排序和外部排序二、内部排序和外部排序三、内部排序方法的分类三、内部排序方法的分类一、何为排序？一、何为排序？将一组“无序无序”的记录序列调整为“有序有序”的记录序列。例如：将如下序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,97二、内部排序和外部排序二、内部排序和外部排序 整个排序过程不须要访问外存便能完成，则为内部排序；反之，若参与排序的记录很多，整个排序过程不行能在内存中完成，称为外部排序。三、内部排序的方法三、内部排序的方法内部排序内部排序的过程实质是一个逐步逐步扩大有序序列长度扩大有序序列长度的过程。经过一趟排序经过一趟排序有序序列区无 序 序 列 区有序序列区无 序 序 列 区基于不同的“扩大扩大”有序序列长度的方法，方法，内部排序内部排序大致可分下列几种类型：插入类插入类交换类交换类选择类选择类归并类归并类其它方法其它方法1.插入类插入类将无序子序列中的一个（或几个）“插入插入”到有序序列中，从而增加有序子序列的长度。2.交换类交换类通过“交换交换”无序序列中的记录以得到其中最小或最大记录，将它加入到有序子序列中，从而增加有序子序列的长度。3.选择类选择类从记录的无序子序列中“选择”最小或最大的记录，将它加入到有序子序列中，从而增加有序子序列的长度。4.归并类归并类 通过“归并归并”两个或两个以上的记录有序子序列，逐步增加有序序列的长度。5.其它方法其它方法 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的插入位置。void InsertionSort(SqList&L)/对依次表对依次表 L 作干脆插入排序。作干脆插入排序。for(i=2;i=L.length;+i)if(L.ri.key L.ri-1.key)/InsertionSortL.r0=L.ri;/设置监视哨for(j=i-1;L.r0.key L.rj.key;-j)L.rj+1=L.rj;/记录后移L.rj+1=L.r0;/插入到正确位置 因为 R1.i-1 是一个有序序列，因此可以利用折半查找折半查找在R1.i-1中找出Ri的插入位置。称这种排序为折半插入排序折半插入排序。二、折半插入排序二、折半插入排序void BiInsertionSort(SqList&L)/BiInsertionSort在在 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;/插入点在高半区三、希尔排序三、希尔排序(又称缩小增量排序又称缩小增量排序)也是一种插入排序方法，但时间困难度也是一种插入排序方法，但时间困难度有较大改进有较大改进基本思想基本思想对无序序列先作对无序序列先作“宏观宏观”调整，后作调整，后作“微观微观”调整调整所谓所谓“宏观宏观”调整，指的是，调整，指的是，“跳动式跳动式”的插入排序的插入排序将序列分成若干子序列，对每个子序列进行插入排序。其中，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 增量为增量为5 5原始序列原始序列8181949411119696121235351717959528285858414175751515子序列子序列1 18181 3535 4141 子序列子序列2 29494 1717 7575 子序列子序列3 31111 9595 1515子序列子序列4 49696 2828 子序列子序列5 51212 5858 结果结果子序列子序列1 13535 4141 8181 子序列子序列2 21717 7575 9494 子序列子序列3 31111 1515 9595子序列子序列4 42828 9696 子序列子序列5 51212 5858 原始序列原始序列3535171711112828121241417575151596965858818194949595增量为增量为3 3原始序列原始序列35171128124175159658819495子序列子序列1 135 28 75 58 95子序列子序列2 217 12 15 81 子序列子序列3 311 41 96 94 结果结果子序列子序列1 128 35 58 75 95子序列子序列2 212 15 17 81 子序列子序列3 311 41 94 96 原始序列原始序列28121135154158179475819695增量为增量为1 1原始序列原始序列28121135154158179475819695子序列子序列1 111121517283441587581949596void ShellInsert(SqList&L,int d)for(i=d+1;i=n;+i)if(L.ri.key0&(L.r0.keyL.rj.key);j-=d)L.rj+d=L.rj;/记录后移，查找插入位置 L.rj+d=L.r0;/插入 /if/ShellInsertvoid ShellSort(SqList&L,int delta,int t)/增量为delta的希尔排序 for(k=0;kt;+t)ShellInsert(L,deltak);/一趟增量为deltak的插入排序/ShellSort 首先对无序序列进行“划分划分”，之后将两个子序列“递归递归”进行快速排序进行快速排序。无 序 的 记 录 序 列无序子序列 1无序子序列 2枢轴枢轴划分分别进行快速排序10.3 快快 速速 排排 序序int partition(int a,int left,int right)/划分划分 int low=left;int high=right;int key=alow;/第一个记录作为枢轴第一个记录作为枢轴 while(low high)while(low=key)high-;alow=ahigh;/将比枢轴小的移到低端将比枢轴小的移到低端 while(low high&alow=right)return;s=partition(a,left,right);Qsort(a,left,s-1);/排序前半部分排序前半部分 Qsort(a,s+1,right);/排序后半部分排序后半部分10.4 选选 择择 排排 序序简 单 选 择 排 序堆 排 序树 形 选 择 排 序一、简洁选择排序一、简洁选择排序有序序列R1.i-1无序序列 Ri.n 第第 i 趟趟从中选出最小的记录有序序列R1.i无序序列 Ri+1.nvoid SelectSort(Elem R,int n)/对记录序列对记录序列R1.n作简洁选择排序。作简洁选择排序。for(i=1;in;+i)/SelectSortj=SelectMinKey(R,i);/在 Ri.n 中选择最小的记录if(i!=j)RiRj;/交换交换二、树形选择排序二、树形选择排序依据锦标赛思想进行的选择排序。三、堆排序三、堆排序堆满足下列性质的序列r1,r2,，rn：或或12,36,27,65,40,34,98,81,73,55,49例如例如:是是小顶堆小顶堆12,36,27,65,40,14,98,81,73,55,49不是堆不是堆(小顶堆小顶堆)(大顶堆大顶堆)rir2i r2i+1 若将该序列视作完全二叉树，则 r2i 是 ri 的左孩子，r2i+1 是 ri 的右孩子。1236276549817355403498例如例如:是堆是堆14不不堆排序堆排序小顶（根）堆堆顶是最小值，输出并从堆上删除，调整剩余的n-1个数据元素序列，使之再次成为小顶堆，即可得到次小值如此反复执行，便能得到一个有序序列大顶（根）堆堆排序的步骤建立堆删除根（具有最小/大值）根和最终一个元素交换（不再是堆）筛选：调整完全二叉树，使之成为堆所谓“筛选筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整调整”根结点根结点使整个二叉树也成为一个堆。堆堆筛筛选选98814973556412362740例如例如:是大顶堆是大顶堆12但在 98 和 12 进行互换之后，它就不不是堆了，因此，须要对它进行“筛选”。98128173641298比较交换建堆是一个从下往上进行建堆是一个从下往上进行“筛选筛选”的过程。的过程。40554973816436122798例如例如:排序之前的关键字序列为123681734998817355 现在，左/右子树都已经调整为堆，最终只要调整根结点，使整个二叉树是个“堆”即可。98494064361227堆排序即是利用堆排序即是利用堆的特性堆的特性对记录序列对记录序列进行排序的一种排序方法。进行排序的一种排序方法。例如：例如：建大顶堆 98,81,49,73,36,27,40,55,64,12 12,81,49,73,36,27,40,55,64,98 交换 98 和 12重新调整为大顶堆 81,73,49,64,36,27,40,55,12,98 40,55,49,73,12,27,98,81,64,36 经过筛选定义堆类型为定义堆类型为:typedef SqList HeapType;/接受依次表表示接受依次表表示 void HeapAdjust(RcdType&R,int s,int m)/已知已知 Rs.m中记录的关键字除中记录的关键字除 Rs 之之外均外均 /满足堆的特征，本函数自上而下调整满足堆的特征，本函数自上而下调整 Rs 的的 /关键字，使关键字，使 Rs.m 也成为一个大顶堆也成为一个大顶堆/HeapAdjustrc=Rs;/暂存 Rs for(j=2*s;j=Rj.key)break;/再作再作“根根”和和“子树根子树根”之间的比较，之间的比较，/若若“=”成立，则说明已找到成立，则说明已找到 rc 的的插插 /入位置入位置 s，不须要接着往下调整，不须要接着往下调整 Rs=Rj;s=j;/否则记录上移，尚需接着往下调整否则记录上移，尚需接着往下调整if(jm&Rj.key0;-i)HeapAdjust(H.r,i,H.length);/建大顶堆for(i=H.length;i1;-i)H.r1H.ri;/将堆顶记录和当前无序序列将堆顶记录和当前无序序列 /H.r1.i中最终一个记录相互交换中最终一个记录相互交换 HeapAdjust(H.r,1,i-1);/对对 H.r1 进行筛选进行筛选10.5 归归 并并 排排 序序归并排序的过程基于下列基本思基本思想想：将两个或两个以上的有序子序列“归并”为一个有序序列。通常接受的是2-路归并排序。即：将两个位置相邻的有序子序列归并为一个一个有序序列。有有 序序 序序 列列 Ri.n有序子序列有序子序列 Ri.m有序子序列有序子序列 Rm+1.n这个操作对依次表而言，是轻而易举的。SRmm+1nTR12ikj15292240 516063418470for(k=i,j=m+1;i=m&j=n;+k)/将SR中记录由小到大地并入TR if(SRi.key=SRj.key)TRk=SRi+;else TRk=SRj+;void Merge(RcdType SR,RcdType&TR,int i,int m,int n)/将有序的记录序列 SRi.m 和 SRm+1.n /归并为有序的记录序列 TRi.n/Mergefor(k=i,j=m+1;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 23归归并并归归并并void 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简洁看出，对 n 个记录进行归并排序的时间困难度为(nlogn)。即：每一趟归并的时间困难度为 O(n)，总共需进行 log2n 趟。10.6 基基 数数 排排 序序基数排序基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。多关键字的排序多关键字的排序链式基数排序链式基数排序一、多关键字的排序一、多关键字的排序 n 个记录的序列个记录的序列 R1,R2,，Rn对关键字对关键字 (Ki0,Ki1,Kid-1)有序有序是指：其中其中:K0 被称为被称为 “最主最主”位关键字位关键字Kd-1 被称为被称为 “最次最次”位关键字位关键字 对于序列中随意两个记录 Ri 和 Rj(1ijn)都满足下列(词典)有序关系：(Ki0,Ki1,Kid-1)(Kj0,Kj1,Kjd-1)多关键字排序通常有两种做法最低位优先最低位优先LSD法法最高位优先最高位优先MSD法 先对先对K0K0进行排序，并按进行排序，并按 K0 K0 的不的不同值将记录序列分成若干子序列之后，同值将记录序列分成若干子序列之后，分别对分别对 K1 K1 进行排序，进行排序，.，依次依次类推，直至最终对最次位关键字排序类推，直至最终对最次位关键字排序完成为止。完成为止。先对 Kd-1 进行排序，然后对 Kd-2 进行排序，.，依次类推，直至对直至对最主位关键字最主位关键字 K0 排序完成为止排序完成为止。假设假设学生记录含三个关键字:系别系别、班号班号和班内的序列号班内的序列号，其中以系别为最主位关键字。LSD的排序过程如下:无序序列无序序列对对K2排序排序对对K1排序排序对对K0排序排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30二、链式基数排序二、链式基数排序假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以接受“支配-收集”的方法，其好处是不须要进行关键字间的比较。对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，接受这种“支配-收集”的方法进行排序，称作基数排序法。例如：例如：对下列这组关键字 209,386,768,185,247,606,230,834,539 首先按其“个位数”取值分别为 0,1,9“支配”成 10 组，之后按从 0 至 9 的依次将它们“收集”在一起；然后按其“十位数”取值分别为 0,1,9 “支配”成 10 组，之后再按从 0 至 9 的依次将它们“收集”在一起；最终按其“百位数”重复一遍上述操作。实现基数排序时，为削减帮助存储空间，应接受链表作存储结构，即链式基数排序，具体作法为：待排序记录以指针相链，构成一个链表；“支配支配”时，按当前时，按当前“关键字位关键字位”取值，取值，将记录支配到不同的将记录支配到不同的“链队列链队列”中，每个队中，每个队列中的列中的“关键字位关键字位”相同；相同；“收集”时，按当前关键字位取值从小到大将各队列首尾相链，构成一个链表;对每个关键字位均重复 2 和 3 两步。例如：p369367167239237138230139进行第一次支配进行第一次支配进行第一次收集进行第一次收集f0 r0f7 r7f8 r8f9 r9p230230367 167237367167237138368239139369 239139138进行其次次支配进行其次次支配p230237138239139p230367167237138368239139f3 r3f6 r6230 237138239139367 167368367167368进行其次次收集 进行第三次收集之后便得到记录的有序序列进行第三次收集之后便得到记录的有序序列f1 r1p230237138239139367167368进行第三次支配进行第三次支配f2 r2f3 r3138 139167230 237239367 368p138139167230237239367368 基数排序的时间困难度为O(d(n+rd)其中：支配为O(n)收集为O(rd)(rd为“基”)d为“支配-收集”的趟数10.7 各种排序方法的比较各种排序方法的比较一、时间性能一、时间性能1.平均的时间性能平均的时间性能基数排序基数排序时间困难度为时间困难度为 O(nlogn)：快速排序、堆排序和归并排序快速排序、堆排序和归并排序时间困难度为时间困难度为 O(n2)O(n2)：干脆插入排序、起泡排序和干脆插入排序、起泡排序和简洁选择排序简洁选择排序时间困难度为时间困难度为 O(n):2.当待排记录序列按关键字依次有序时当待排记录序列按关键字依次有序时3.简洁选择排序、堆排序和归并排序的简洁选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布时间性能不随记录序列中关键字的分布而变更。而变更。干脆插入排序和起泡排序能达到O(n)的时间困难度，若枢轴选取不当，快速排序的时间性能会蜕化为O(n2)。二、空间性能二、空间性能指的是排序过程中所需的帮助空间大小1.全部的简洁排序方法全部的简洁排序方法(包括：干脆插包括：干脆插入、入、起泡和简洁选择起泡和简洁选择)和堆排序的空间困难和堆排序的空间困难度为度为O(1)；2.快速排序为快速排序为O(logn)，为递归程序执，为递归程序执行过程中，栈所需的帮助空间；行过程中，栈所需的帮助空间；3.归并排序所需帮助空间最多，其空归并排序所需帮助空间最多，其空间困难度为间困难度为 O(n);4.链式基数排序需附设队列首尾指链式基数排序需附设队列首尾指针，则空间困难度为针，则空间困难度为 O(rd)。三、排序方法的稳定性三、排序方法的稳定性 1.稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有变更。排序之前: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)则称该排序方法是不稳定不稳定的。2.对于不稳定的排序方法，只要能举出一个实例说明即可。3.快速排序、堆排序和希尔排序是不稳快速排序、堆排序和希尔排序是不稳定的排序方法定的排序方法。例如例如:对 4,3,4,2 进行快速排序，得到 2,3,4,4