第十章排序(精品).ppt

第十章第十章 内部排序内部排序10.1 排序的定义和方法 排序是将无序的记录序列调整为有序记录序列的一种操作。稳定的排序方法稳定的排序方法：对于两个关键字相等的记录在经过排序之后，不改变它们在排序之前在序列中的相对位置。不稳定的排序方法：不稳定的排序方法：对于两个关键字相等的记录在经过排序之后，改变了它们在排序之前在序列中的相对位置。根据在排序过程中涉及的存储器不同，可将排序方法分为两大类：1）内部排序：内部排序：在排序进行的过程中不使用计算机外部存储器的排序过程。2）外部排序：外部排序：在排序进行的过程中需要对外存进行访问的排序过程。本章仅讨论各种内部排序的方法。内部排序的过程是一个逐步扩大记录的“有序序列”区域的长度的过程。大多数排序方法在排序过程中将出现如动画所示“有序”和“无序”两个区域。演示10.2 插入排序 插入排序的准则是，在有序序列中插入新的记录以达到扩大有序区的长度的目的。10.2.1 直接插入排序直接插入排序一趟直接插入排序的基本思想则是:在对记录序列R1.n的排序过程中，区段R1.i-1中的记录已按关键字非递减的顺序排列，将 Ri 插入到有序序列 R1.i-1 中，使区段 R1.i 中的记录按关键字非递减顺序排列。演示实现一趟插入排序的步骤为：1)在 R1.i-1 中查找 Ri 的插入位置，即确定j(0ji)使得R1.j.keyRi.keyRj+1.i-1.key2)将 Rj+1.i-1 中的记录后移一个位置；3)将 Ri 插入到 j+1 的位置。算法算法10.2void InsertSort(SqList&L)/对顺序表对顺序表L作直接插入排序作直接插入排序for(i=2;i=L.length;+i)if(L.ri.key L.ri-1.key)/将 L.ri 插入有序子表L.r0=L.ri;L.ri=L.ri-1;for(j=i-2;L.r0.key L.rj.key;-j)L.rj+1=L.rj;/记录后移L.rj+1=L.r0;/插入到正确位置/if/InsertSort直接插入排序的时间复杂度：直接插入排序的时间复杂度：当待排记录处于“正序”(即记录按关键字从小到大的顺序排列)的情况时，所需进行的关键字比较和记录移动的次数最少（分别为：n-1，0），反之，当待排记录处于“逆序”(即记录按关键字从大到小的顺序排列)的情况时，所需进行的关键字比较和记录移动的次数最多（分别为：，）；若待排记录序列处于随机状态，则可以最坏和最好的情况的平均值作为插入排序的时间性能的量度。一般情况下，直接插入排序的时 间复杂度为O(n2)。10.2.2 折半插入排序折半插入排序演示演示算法算法 10.3void BInsertSort(SqList&L)/对顺序表对顺序表L作折半插入排序作折半插入排序for(i=2;i=L.length;+i)L.r0=L.ri;/将L.ri暂存到L.r0low=1;high=i-1;while(low=high)/在rlow.high中折半查找有序插入的位置m=(low+high)/2;/折半if(L.r0.key=low;-j)L.rj+1=L.rj;/记录后移L.rhigh+1=L.r0;/插入/BInsertSort折半插入排序只能减少排序过程中关键字比较的时间，并不能减少记录移动的时间，因此折半插入排序的时间复杂度仍为O(n2)。10.2.5 希尔排序希尔排序希尔排序又称“缩小增量排序”，它的 基本思想是，先对待排序列进行“宏观调整”，待序列中的记录“基本有序”时再进行直接插入排序。演示 例如一个含11个关键字的序列(16，25，12，30，47，11，23，36，9，18，31)的希尔排序过程演示 算法算法 10.5void ShellInsert(SqList&L，int dk)/对顺序表对顺序表L作一趟增量为作一趟增量为dk的希尔排序的希尔排序 for(i=dk+1;i=L.length;+i)if(L.ri.key 0&L.r0.key L.rj.key;j-=dk)L.rj+dk=L.rj;/记录后移L.rj+dk=L.r0;/插入到正确位置/if/ShellInsert算法算法 10.6void ShellSort(SqList&L,int dlta,int t)/按增量序列按增量序列 dlta0.t-1 对顺序表对顺序表L作希尔排序作希尔排序for(k=0;kt;+t)ShellInsert(L,dltak);/一趟增量为 dltak 的插入排序/ShellSort希尔排序的时间复杂度和所取增量序列相关，例如已有学者证明，当增量序列为 2t-k-1(k=0,1,，t-1)时，希尔排序的时间复杂度为O(n3/2)。10.3 快速排序10.3.1 起泡排序起泡排序演示 演示 在待排记录处于“正序”时取最小值，此时只需进行一趟起泡排序（比较和移动次数分别为n-1和0），反之，在待排记录处于“逆序”时取最大值，此时需进行 n-1趟起泡（比较和移动次数分别为 和 ）。10.3.2 快速排序快速排序快速排序则是通过一趟排序选定一个关键字 介于“中间”的记录，从而使剩余记录可以分成两 个子序列分别继续排序，通常称该记录为“枢轴”。关键字序列(52,49,80,36,14,75,58,97,23,61)经第1趟快速排序之后为(23,49,14,36)52(75,58,97,80,61)经第2趟快速排序之后为(14)23(49,36)52(61,58)75(80,97)经第3趟快速排序之后为(14,23,36,49,52,58,61,75,80,97)算法算法 10.9void QSort(RcdType R,int s,int t)/对记录序列对记录序列 Rs.t 进行快速排序进行快速排序if(s t)/长度大于1pivotloc=Partition(R,s,t);/对 Rs.t 进行一趟快排，并返回枢轴位置QSort(R,s,pivotloc-1);/对低子序列递归进行排序QSort(R,pivotloc+1,t);/对高子序列递归进行排序/if/Qsort 算法算法 10.10void QuickSort(SqList&L)/对顺序表对顺序表 L 进行快速排序进行快速排序QSort(L.r,1,L.length);/QuickSort一次划分（一趟快速排序）的算法如下：一次划分（一趟快速排序）的算法如下：算法算法 演示演示int Partition(RcdType R,int low,int high)/对记录子序列对记录子序列 Rlow.high 进行一趟快速排序，并返回枢轴记录进行一趟快速排序，并返回枢轴记录/所在位置，使得在它之前的记录的关键字均不大于它的关键字，所在位置，使得在它之前的记录的关键字均不大于它的关键字，/而在它之后的记录的关键字均不小于它的关键字而在它之后的记录的关键字均不小于它的关键字R0=Rlow;/将枢轴记录移至数组的闲置分量pivotkey=Rlow.key;/枢轴记录关键字while(lowhigh)/从表的两端交替地向中间扫描while(low=pivotkey)-high;Rlow+=Rhigh;/将比枢轴记录小的记录移到低端while(lowhigh&Rlow.key=pivotkey)+low;Rhigh-=Rlow;/将比枢轴记录大的记录移到高端/whileRlow=R0;/枢轴记录移到正确位置return low;/返回枢轴位置/Partition可以推证，快速排序的平均时间复杂度为O(nlogn)，在三者取中的前 提下，对随机的关键字序列，快速排序是目前被认为是最好 的排序方法。10.4 选择排序法 10.4.1 简单选择排序简单选择排序选择排序的基本思想是，在待排区段的记录序列中选出关键字最大或最小的记录，并将它移动到法定位置。第 i(i=1,2,n-1)趟的简单选择排序（序列中前 i-1 个记录的关键字均小于后 n-i+1 个记录的关键字）的作法是，在后 n-i+1 个记录中选出关键字最小的记录，并将它和第 i 个记录进行互换。算法算法 10.12void SelectSort(SqList&L)/对顺序表对顺序表L作简单选择排序作简单选择排序for(i=1;iL.length;+i)/选择第 i 小的记录，并交换到位j=i;for(k=i+1;k=L.length;k+)/在L.ri.L.length中选择关键字最小的记录if(L.rk.key L.rj.key)j=k;if(i!=j)L.rj L.ri;/与第 i 个记录互换/for/SelectSort10.4.2 树形选择排序树形选择排序10.4.3 堆排序堆排序若含n个元素的序列 k1,k2,kn 满足下列关系则称作“小顶堆”或“大顶堆”。“堆顶”元素为序列中的“最小值”或“最大值”。如：12,39,20,65,47,34,98,81,73,56为“小顶堆”；98,81,34,73,56,12,20,39,65,47为“大顶堆”。可将上述数列视为如下的一个完全二叉树：利用堆的特性进行的排序方法即为“堆排序”，其排序过程如下：假设待排关键字序列为：34,39,20,65,47,12,98,73,81,56 1）先将它调整为大顶堆：98,81,34,73,56,12,20,39,65,47 2）互换“堆顶”和待排序列中 的最后的关键字：47,81,34,73,56,12,20,39,65,98 3）在待排序列中舍去最大关键字，将其余部分重新调整为堆：81,73,34,65,56,12,20,39,47 984）重复2）和3）直至待排序列中只剩一个关键字为止。堆排序的两个关键问题是：1）如何将一个无序序列调整为堆？2）如何在互换堆顶之后重新调整为堆？演示演示 算法算法 10.13void HeapAdjust(SqList&H,int s,int m)/已知已知H.rs.m中记录的关键字除中记录的关键字除H.rs.key之外均满足堆的定义，之外均满足堆的定义，/本函数依据关键字的大小对本函数依据关键字的大小对H.rs进行调整，使进行调整，使H.rs.m成为一成为一/个大顶堆（对其中记录的关键字而言）个大顶堆（对其中记录的关键字而言）H.r0=H.rs;/暂存根结点的记录for(j=2*s;j=m;j*=2)/沿关键字较大的孩子结点向下筛选if(jm&H.rj.key=H.rj.key)break;/不需要调整，跳出循环H.rs=H.rj;s=j;/将大关键字记录往上调/forH.rs=H.r0;/回移筛选下来的记录/HeapAdjust 算法算法 10.14 演示void HeapSort(SqList&H)/对顺序表对顺序表H进行堆排序进行堆排序for(i=H.length/2;i0;-i)/将 H.r1.H.length 建成大顶堆HeapAdjust(H,i,H.length);H.r1 H.rH.length;/互换堆顶和堆底的记录for(i=H.length-1;i1;-i)HeapAdjust(H,1,i);/从根开始调整，将 H.r1.i 重新调整为大顶堆H.r1 H.ri;/互换“堆顶”和当前的“堆底”，使已有序的记录沉积在底部/for/HeapSort可以证明，堆排序的时间复杂度为O(nlogn)。和选择排序同，无 论待排序列中的记录是正序还是逆序排列，都不会使堆排序 处于最好或最坏的状态。10.5 归并排序法 10.5.1 2-路归并排序路归并排序 归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。2-路归并排序则是归并排序中的一种最简单的情况，它的基本操作是将两个相邻的有序子序列“归并”为一个有序序列。算法算法 10.15void Merge(RcdType SR,RcdType TR,int i,int m,int n)/将有序的将有序的SRi.m和和SRm+1.n归并为有序的归并为有序的TRi.nfor(j=m+1,k=i;i=m&j=n;+k)/将SR中记录按关键字从小到大地复制到TR中if(SRi.key=SRj.key)TRk=SRi+;else TRk=SRj+;while(i=m)TRk+=SRi+;/将剩余的 SRi.m 复制到TRwhile(j=n)TRk+=SRj+;/将剩余的 SRj.n 复制到TR/Merge算法算法 10.16演示演示void Msort(RcdType SR,RcdType TR1,int s,int t)/对对SRs.t进行归并排序，排序后的记录存入进行归并排序，排序后的记录存入TR1s.tif(s=t)TR1s=SRs;else 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.t/else/Msort 算法算法 10.17void MergeSort(SqList&L)/对顺序表对顺序表L作作2-路归并排序路归并排序MSort(L.r,L.r,1,L.length);/MergeSort10.6 基数排序 10.6.1 多关键字的排序多关键字的排序通常实现多关键字排序可以有两种策略：一是最主位优先主位优先（MSD法）另一是最次位优先最次位优先（LSD法）。演示 假设记录的逻辑关键字由 d 个“关键字”构成，每个关键字可能取 rd 个值，则只要从最低位关键字最低位关键字起，按关键字的不同值将记录“分配”到 rd 个队列之后再“收集”在一起，如此重复 d 趟，最终完成整个记录序列的排序。按这种方法实现的排序称为“基基数排序数排序”，其中“基数基数”即 rd 指的是“关键字”的取值范围。演示 10.6.2 链式基数排序演示 附设指针数组将顺序表视作一个静态链表，利用修改指针实现分配和收集。同时设置rd个队列的头指针和尾指针，分别指示各队列的头结点和尾结点在链表中的位置。算法算法 10.19void Distribute(RcdType R,int k,int f,int e)/R 中记录已按中记录已按(R.keysk+1,.,R.keysL.bitsnum-1)有序，有序，/本算法按本算法按 R.keysk 建立建立 RADIX 个子表，使同一子表中记录的个子表，使同一子表中记录的/keysk 相同。相同。f0.RADIX-1 和和 e0.RADIX-1 分别指向各子分别指向各子/表中第一个和最后一个记录表中第一个和最后一个记录for(j=0;jRadix;+j)fj=0;/各子表初始化为空表for(p=Next0;p;p=Nextp)j=ord(Rp.keysk);/ord 将记录中的关键字keysk映射到0.RADIX-1中if(!fj)fj=p;else Nextej=p;ej=p;/将 p 所指的结点插入相应子表/for/Distribute算法算法 10.20void Collect(RcdType R,int k,int f,int e)/本算法按本算法按 R.keysk 自小至大地将自小至大地将 f0.RADIX-1 所指各子表所指各子表/依次链接成一个链表，依次链接成一个链表，e0.RADIX-1 为各子表的尾指针为各子表的尾指针for(j=0;!fj;j=succ(j);/找第一个非空子表，succ 为求后继函数Next0=fj;t=ej;/Next0指向第一个非空子表中第一个结点 while(jRADIX)for(j=succ(j);jRADIX-1&!fj;j=succ(j);/找下一个非空子表if(fj)rt.next=fj;t=ej;/链接两个非空子表/whileNextt=0;/t 指向最后一个非空子表中的最后一个结点/Collect链式基数排序的时间复杂度为O(d(n+rd)，或简写为O(dn)。10.7 各种排序方法的综合比较 一、一、时间性能时间性能 1.按平均的时间性能来分，有三类排序方法：时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中快速排序目前被认为是最快的一种排序方法，后两者之比较，在 n 值较大的情况下，归并排序较堆排序更快；时间复杂度为O(n2)的有：插入排序、起泡排序和选择排序，其中以插入排序为最常用，特别是对于已按关键字基本有序排列的记录序列尤为如此，选择排序过程中记录移动次数最少；时间复杂度为O(n)的排序方法只有基数排序一种。2.当待排记录序列按关键字顺序有序时，插入 排序和起泡排序能达到O(n)的时间复杂度；而对 于快速排序而言，这是最不好的情况，此时的时 间性能蜕化为O(n2)，因此应尽量避免。3.选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。4.以上对排序的时间复杂度的讨论主要考虑排序过程中所需进行的关键字间的比较次数，当待排序记录中其它各数据项比关键字占有更大的数据量时，还应考虑到排序过程中移动记录的操作时间，有时这种操作的时间在整个排序过程中占的比例更大，从这个观点考虑，简单排序的三种排序方法中起泡排序效率最低。二、空间性能二、空间性能指的是排序过程中所需的辅助空间大小。1.所有的简单排序方法（包括：插入、起泡和选择排序）和堆排序的空间复杂度均为O(1)。2.快速排序为O(logn)，为递归程序执行过程中栈所需的辅助空间。3.归并排序和基数排序所需辅助空间最多，其空间复杂度为O(n)。三、排序方法的稳定性能三、排序方法的稳定性能1.除希尔排序、快速排序和堆排序是不稳定的排序方法外，本章讨论的其它排序方法都是稳定的。例如：对关键字序列(41,3,42,2)进行快速排序，其结果为(2,3,42,41)。2.稳定性是由方法本身决定的。一般来说，排序过程中所进行的比较操作和交换数据仅发生在相邻的记录之间，没有大步距的数据调整时，则排序方法是稳定的。而对不稳定的排序方法，不论其算法的描述形式如何，总能举出一个说明它不稳定的实例来。【本章小结本章小结】本章主要讨论各种内部排序的方法。学习本章的目的是了解各种排序 方法的原理以及各自的优缺点，以便在编制软件时能按照情况所需合理选用。一般来说，在选择排序方法时，可有下列几种选择：1)若待排序的记录个数n值较小（例如n30），则可选用插入排序法，但若记录所含数据项较多，所占存储量大时，应选用选择排序法。反之，若待排序的记录个数n值较大时，应选用快速排序法。但若待排序记录关键字有有序倾向时，就慎用快速排序，而宁可选用堆排序或归并排序，而后两者的最大差别是所需辅助空间不等。2)快速排序和归并排序在n值较小时的性能不及直接插入排序，因此在实际应用时，可将它们和插入排序混合使用。如在快速排序划分子区间的长度小于某值时，转而调用直接插入排序；或者对待排记录序列先逐段进行直接插入排序，然后再利用归并操作进行两两归并直至整个序列有序为止。3)基数排序的时间复杂度为O(dn)，因此特别适合于待排记录数 n 值很大，而关键字位数 d 较小的情况。并且还可以调整基数（如将基数定为100或1000等）以减少基数排序的趟数d的值。4)一般情况下，对单关键字进行排序时，所用的排序方法是否稳定无关紧要。但当按最次位优先进行多关键字排序时(除第一趟外)必须选用稳定的排序方法。