第8章-排序要点优秀PPT.ppt

第八章第八章 排序排序DS应用实践应用实践插入排序插入排序 基数排序基数排序归并排序归并排序交换排序交换排序选择排序选择排序Hot Tip 本章学习的要点主要是了解各种排序方法实现时所依据的原则以及它们的主要操作（关键字间的比较和记录的移动）的时间分析。学习中应留意驾驭各种排序方法实现的要点，切实驾驭各种排序过程的排序特点所在。8.1基本概念基本概念v排序排序(Sorting)定义：是将一个数据元素（或记录）的定义：是将一个数据元素（或记录）的随意序列，重新排列成一个按关键字有序的序列。随意序列，重新排列成一个按关键字有序的序列。v关键字：数据元素中的某个数据项。关键字：数据元素中的某个数据项。v 内部排序内部排序：待排序的记录存放在计算机随机存储器中进：待排序的记录存放在计算机随机存储器中进行的排序过程。行的排序过程。外部排序外部排序：待排序记录的数量很大，以致内存一次不能：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。序过程。493865977613274913273849496576971327384949657697方法一：方法一：方法二：方法二：原始序列：原始序列：假设假设Ki=Kj(ij)，且在排序前的序列中，且在排序前的序列中Ri领先于领先于Rj(即即i8？8？8？579101314845213905514131098Ri这方法简洁易懂，但效率不高，比如将下一元素这方法简洁易懂，但效率不高，比如将下一元素45插入到当前的有插入到当前的有序表。假如将当前待插入的元素序表。假如将当前待插入的元素Ri与有序区中的元素从后往前进与有序区中的元素从后往前进行比较，若行比较，若RiRi-1则停止比较，则停止比较，Ri呆在原位不动即可呆在原位不动即可;若若RiRi-1则接着往前进行比较，且进行比较的同时将被比较过的则接着往前进行比较，且进行比较的同时将被比较过的元素后移一位置，直到元素后移一位置，直到Ri大于其中某一元素大于其中某一元素Rk为止，为止，Ri则插入则插入到到Rk+1的位置上。的位置上。voidInsertSort(SqList*L)inti,j;for(i=2;ilength;i+)if(L-riri-1)L-r0=L-ri;/设置哨兵设置哨兵for(j=i-1;L-rjL-r0;j-)L-rj+1=L-rj;L-rj+1=L-r0;例例49386597761327i=2(49)386597761327i=1()4938R038j例例49386597761327i=2(4938)6597761327i=3(3849）6597761327i=4(384965）97761327i=5(38496597）761327i=613(133849657697)27i=1()i=7(13273849657697)279776R0766597voidInsertSort(SqList*L)inti,j;for(i=2;ilength;i+)if(L-riri-1)L-r0=L-ri;/设置哨兵设置哨兵for(j=i-1;L-rjL-r0;j-)L-rj+1=L-rj;L-rj+1=L-r0;算法算法8.1干脆插入排序干脆插入排序干脆插入排序算法简洁、简洁实现，只须要一个记录干脆插入排序算法简洁、简洁实现，只须要一个记录大小的协助空间用于存放待插入的记录（在大小的协助空间用于存放待插入的记录（在C语言中，我语言中，我们利用了数组中的们利用了数组中的0单元）和两个单元）和两个int型变量。当待排序记型变量。当待排序记录较少时，排序速度较快，但是，当待排序的记录数量较录较少时，排序速度较快，但是，当待排序的记录数量较大时，大量的比较和移动操作将使干脆插入排序算法的效大时，大量的比较和移动操作将使干脆插入排序算法的效率降低；然而，当待排序的数据元素基本有序时，干脆插率降低；然而，当待排序的数据元素基本有序时，干脆插入排序过程中的移动次数大大削减，从而效率会有所提高。入排序过程中的移动次数大大削减，从而效率会有所提高。插入排序是一种稳定的排序方法。插入排序是一种稳定的排序方法。当待排记录处于当待排记录处于正序正序(即记录按关键字从小到大的即记录按关键字从小到大的依次排列依次排列)的状况时，所需进行的关键字比较和记录移动的状况时，所需进行的关键字比较和记录移动的次数最少，反之，当待排记录处于的次数最少，反之，当待排记录处于逆序逆序(即记录按关即记录按关键字从大到小的依次排列键字从大到小的依次排列)的状况时，所需进行的关键字的状况时，所需进行的关键字比较和记录移动的次数最多，如下表所列。比较和记录移动的次数最多，如下表所列。待排记录序列处于随机状态，则可以最坏和最好的状待排记录序列处于随机状态，则可以最坏和最好的状况的平均值作为插入排序的时间性能的量度。一般状况下，况的平均值作为插入排序的时间性能的量度。一般状况下，干脆插入排序的时间困难度为干脆插入排序的时间困难度为O(n2)。v希尔排序希尔排序(ShellSort)又称为又称为“缩小增量排序缩小增量排序”(DiminishingIncrementSort)v基本思想：先将整个待排记录分割成为若干个子序列基本思想：先将整个待排记录分割成为若干个子序列分别进行直分别进行直接插入排序，待整个序列中的记录接插入排序，待整个序列中的记录“基本有基本有序序”时，再对全体记录进行一次干脆插入排序。时，再对全体记录进行一次干脆插入排序。8.2.3希尔排序希尔排序v具体步骤具体步骤v 假设待排序的记录为假设待排序的记录为n个，先取整数个，先取整数dR2，则则交交换换；然然后后比比较较其其次次个个记记录录与与第第三三个个记记录录；依依次次类类推推，直直至至第第n-1个个记记录录和和第第n个个记记录录比比较较为为止止第第一一趟趟冒冒泡泡排排序序，结结果果关关键键字字最最大大的的记录被安置在最终一个记录上记录被安置在最终一个记录上对对前前n-1个个记记录录进进行行其其次次趟趟冒冒泡泡排排序序，结结果果使使关关键键字字次次大大的记录被安置在第的记录被安置在第n-1个记录位置个记录位置重重复复上上述述过过程程，直直到到“在在一一趟趟排排序序过过程程中中没没有有进进行行过过交交换换记录的操作记录的操作”为止为止 用冒泡排序算法用冒泡排序算法对数据表数据表A=(12,5,4,9,5)从小到从小到大大进行排序。行排序。解：9559445512 412595124512594512125945912125voidBubbleSortC(SqList*L)inti,j;for(i=1;ilength;i+)for(j=L-length-1;j=i;j-)if(L-rjL-rj+1)swap(L,j,j+1);/交换交换j与与j+1的值的值voidBubbleSortC(SqList*L)inti,j;intflag=TRUE;for(i=1;ilength&flag;i+)flag=FALSE;for(j=L-length-1;j=i;j-)if(L-rjL-rj+1)swap(L,j,j+1);/交换交换j与与j+1的值的值flag=TRUE;/有数据交换，循环接着有数据交换，循环接着算法评价算法评价时间困难度时间困难度最好状况（正序）最好状况（正序）比较次数：比较次数：n-1移动次数：移动次数：012345最坏状况（逆序）最坏状况（逆序）比较次数：比较次数：Y移动次数：移动次数：空间困难度：空间困难度：S(n)=O(1)T(n)=O(n)54321v冒泡排序比较简洁，当时始序列基本有序时，冒泡冒泡排序比较简洁，当时始序列基本有序时，冒泡排序有较高的效率，反之效率较低；其次冒泡排序排序有较高的效率，反之效率较低；其次冒泡排序只须要一个记录的协助空间，用来作为记录交换的只须要一个记录的协助空间，用来作为记录交换的中间暂存单元；冒泡排序是一种稳定的排序方法。中间暂存单元；冒泡排序是一种稳定的排序方法。v冒泡排序时间困难度的分析：当最好的状况时，也冒泡排序时间困难度的分析：当最好的状况时，也就是要排序的表本身就是有序的，时间困难度为就是要排序的表本身就是有序的，时间困难度为O(n)。当最坏的状况时，即待排序表是逆序的状况，。当最坏的状况时，即待排序表是逆序的状况，此时须要比较此时须要比较次，并作次，并作等数量级的记录移动。因此，总的时间困难度为等数量级的记录移动。因此，总的时间困难度为O(n2)。快速排序快速排序（划分交换排序）（划分交换排序）基本思想：在当前无序区基本思想：在当前无序区R1k任取一个记录作为比较任取一个记录作为比较的的“基准基准”，用此基准将当前无序区划分为左右两个较，用此基准将当前无序区划分为左右两个较小的无序子区：小的无序子区：R1i-1和和Ri+1k，而基准在，而基准在Ri。要。要求左边的无序子区中记录的关键字均小于或等于基准，求左边的无序子区中记录的关键字均小于或等于基准，右边的无序子区中记录的关键字均大于或等于基准的关右边的无序子区中记录的关键字均大于或等于基准的关键字。键字。8.3.2快速排序（划分交换排序）快速排序（划分交换排序）排排序序过过程程：设设待待排排序序列列为为:Rs,Rs+1,Rt，附附设设两两个个指针指针low和和high，设基准（枢轴）记录，设基准（枢轴）记录tp=随意序列元素随意序列元素初始时令初始时令low=s,high=t首首先先从从high所所指指位位置置向向前前搜搜寻寻第第一一个个关关键键字字小小于于tp.key的的记录，并和记录，并和tp交换交换例例初始关键字：初始关键字：4938659776132750基准基准tplowhigh27hightp.ktp.klow974次交换后：次交换后：27381376976550lowhighhigh()tp=4949再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止完成一趟排序：完成一趟排序：(273813)49(76976550)分别进行快速排序：分别进行快速排序：(13)27(38)49(5065)76(97)快速排序结束：快速排序结束：1327384950657697算法描述算法描述intPartition(SqList*L,intlow,inthigh)intpivotkey;pivotkey=L-rlow;while(lowhigh)while(lowrhigh=pivotkey)high-;swap(L,low,high);while(lowrlow=pivotkey)low+;swap(L,low,high);returnlow;快速排序算法分析快速排序算法分析 p稳定性：不定性：不稳定排序。定排序。p时间困困难度：度：p一般状况一般状况(每次等分子表每次等分子表):O(nlog2n)p最坏状况（初始序列有序）：最坏状况（初始序列有序）：O(n2)p空空间性能：性能：1个个协助空助空间。8.4选择排序选择排序v基本思想：每一趟在n-i+1(i=1,2,n)个记录中选取关键字最小的记录作有序序列中的第i个记录v干脆选择排序v首先通过n-1次关键字比较，从无序区R1n 中找出关键字最小的记录，将它与第一个记录交换v再通过n-2次比较，从无序区R2n中找出关键字次小的记录，将它与其次个记录交换v重复上述操作，共进行n-1趟排序后，最终序列变成有序序列，排序结束。例例初始：初始：49386597761327kjjjjjji=11349一趟：一趟：13386597764927i=2kkjjjjj2738二趟：二趟：13276597764938三趟：三趟：13273897764965四趟：四趟：13273849769765五趟：五趟：13273849659776六趟：六趟：13273849657697排序结束：排序结束：13273849657697k：记录当前最小记录的位置：记录当前最小记录的位置kkvoidSelectSort(SqList*L)inti,j,min;for(i=1;ilength;i+)min=i;for(j=i+1;jlength;j+)if(L-rminL-rj)min=j;if(i!=min)swap(L,i,min);v算法评价算法评价v时间困难度时间困难度v记录移动次数记录移动次数空间困难度：S(n)=O(1)T(n)=O(n)1357911（有序）（有序）7911531（正反序）（正反序）干脆选择排序不稳定，例如：2 2 1Y最好状况：最好状况：0:Y最坏状况：最坏状况：3(n-1):比较次数：比较次数：8.4.2堆排序堆排序v堆的定义：n个元素的序列k1,k2,kn，当且仅当满足下列关系时，称之为堆。或或8.4.2堆排序堆排序例例96，83，27，38，11，996279113883若将序列对应的一维数组看成是一个完全二叉树的若将序列对应的一维数组看成是一个完全二叉树的依次存储结构，则堆的含义表明，完全二叉树中全依次存储结构，则堆的含义表明，完全二叉树中全部非终端结点的值均不大于（或不小于）其左、右部非终端结点的值均不大于（或不小于）其左、右孩子的结点的值。故，堆顶元素必为序列的最小孩子的结点的值。故，堆顶元素必为序列的最小（大）值。（大）值。v小根堆v大根堆 (a)小根堆的逻辑结构 (b)小根堆的存储结构(a)大根堆的逻辑结构 (b)大根堆的存储结构v堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重新建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫v堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？为一个新的堆？v第一个问题解决方法第一个问题解决方法v方法：从无序序列的第方法：从无序序列的第 n/2 个元素（即此无序序列对个元素（即此无序序列对应的完全二叉树的最终一个非应的完全二叉树的最终一个非v终端结点）起，至第一个元素止，进行反复筛选终端结点）起，至第一个元素止，进行反复筛选例例含含8个元素的无序序列（个元素的无序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133827657650971327384965765097v其次个问题解决方法其次个问题解决方法筛选筛选v方法：输出堆顶元素之后，以堆中最终一个元素替方法：输出堆顶元素之后，以堆中最终一个元素替代之；然后将根结点值与左、右子树的根结点值进行代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为整过程为“筛选筛选”例例13273849657650974997273865765013输出：输出：132749389765765013输出：输出：131397493827657650输出：输出：13273849502765769713输出：输出：13276549502738769713输出：输出：1327384965502738769713输出：输出：1327387665502738499713输出：输出：132738495065762738499713输出：输出：132738499765762738495013输出：输出：13273849506597762738495013输出：输出：13273849509765762738495013输出：输出：1327384950657665972738495013输出：输出：1327384950659765762738495013输出：输出：132738495065769765762738495013输出：输出：13273849506576974997273865765013输出：输出：13(1)由无序到有序的筛选过程实现由无序到有序的筛选过程实现void HeapAdjust(SqList*L,int s,int m)int temp,j;temp=L-rs;for(j=2*s;j=m;j*=2)if(jrjrj+1)+j;if(temp=L-rj)break;L-rs=L-rj;s=j;L-rs=temp;(2)堆排序的过程堆排序的过程void HeapSort(SqList*L)int i;for(i=L-length/2;i0;i-)HeapAdjust(L,i,L-length);for(i=L-length;i1;i-)swap(L,1,i);HeapAdjust(L,1,i-1);v时间困难度：最坏状况下T(n)=O(nlogn)v空间困难度：S(n)=O(1)v不稳定v适用于记录数较大的状况8.5 归并排序v一趟归并将两个或两个以上的有序表组合成一个新的有序表，叫v2-路归并排序设初始序列含有设初始序列含有n个记录，则可看成个记录，则可看成n个有序的个有序的子序列，每个子序列长度为子序列，每个子序列长度为1两两合并，得到两两合并，得到 n/2 个长度为个长度为2或或1的有序子的有序子序列序列再两两合并，再两两合并，如此重复，直至得到一个长如此重复，直至得到一个长度为度为n的有序序列为止的有序序列为止例例初始关键字：初始关键字：49386597761327一趟归并后：一趟归并后：38496597137627二趟归并后：二趟归并后：38496597132776三趟归并后：三趟归并后：13273849657697LALBLCikjj+1i+1将两个有序子表将两个有序子表SRi.m和和SRm+1.n合并为一个合并为一个有序表有序表TRi.nvoidMerge(intSR,intTR,inti,intm,intn)intj,k,l;for(j=m+1,k=i;i=m&j=n;k+)if(SRiSRj)TRk=SRi+;elseTRk=SRj+;while(i=m)TRk+l=SRi+l;while(j=n)TRk+l=SRj+l;(1)一趟归并问题一趟归并问题void MergePass(int SR,int TR,int s,int n)int i=1;int j;while(i=n-2*s+1)Merge(SR,TR,i,i+s-1,i+2*s-1);i=i+2*s;if(in-s+1)Merge(SR,TR,i,i+s-1,n);else /最终只剩下单个子序列for(j=i;j=n;j+)TRj=SRj;8.6基数排序基数排序v例 对52张扑克牌按以下次序排序：23A 23A23A 23A两个关键字：花色（）面值（23A）并且“花色”地位高于“面值”多关键字排序 一般状况下，假设有n个记录的序列R1，R2，Rn且每个记录Ri中含有d个关键字（Ki0,Ki1，Kid-1），则称序列R1,R2,Rn对关键字（Ki0,Ki1,Kid-1）有序是指：对于序列中随意两个记录Ri和Rj(1ijn)都满足下列有序关系：(Ki0,Ki1，Kid-1)(Kj0,Kj1，Kjd-1)其中，K0称为最主位关键字，Kd-1称为最次位关键字。如：5位十进制数92101、23656，它们含有5个关键字，分别是万、千、百、十、个位，其中万位是最主位关键字，个位是最次位关键位v排序方法 从最低位关键字kd-1起进行排序，然后再对高一位的关键字排序，依次重复，直至对最高位关键字k0排序后，便成为一个有序序列8.6.2 链式基数排序v基数排序：借助“安排”和“收集”对单逻辑关键字进行排序的一种方法。v链式基数排序：用链表作存储结构的基数排序v链式基数排序步骤（对十进制数而言）v设置10个队列，fi和ei分别为第i个队列的头指针和尾指针v第一趟安排对最低位关键字（个位）进行，变更记录的指针值，将链表中记录安排至10个链队列中，每个队列记录的关键字的个位相同8.6.2 链式基数排序第一趟收集是变更全部非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表重复上述两步，进行其次趟、第三趟安排和收集，分别对十位、百位进行，最终得到一个有序序列例例初始状态初始状态278109063930589184505269008083109278063930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配尾指针尾指针头指针头指针初始状态初始状态278109063930589184505269008083109278063930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配尾指针尾指针头指针头指针589184505初始状态初始状态278109063930589184505269008083109278063930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配尾指针尾指针头指针头指针589184505269初始状态初始状态278109063930589184505269008083109278063930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配尾指针尾指针头指针头指针589184505269008083930063083184505278008109589269一趟收集：一趟收集：505008109930063269278083184589二趟收集：二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二二趟趟分分配配008109278930063083184505278008109589269一趟收集的结果：一趟收集的结果：008063083109184269278505589930三趟收集：三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三三趟趟分分配配063083269278505589505008109930063269278083184589二趟收集的结果：二趟收集的结果：算法评价时间困难度：安排：T(n)=O(n)收集：T(n)=O(rd)T(n)=O(d(n+rd)其中：n记录数 d关键字数 rd关键字取值范围 空间困难度：S(n)=2rd个队列指针+n个指针域空间8.7 各种内部排序方法的比较排序方法平均时间最好情况最坏情况辅助空间直接插入排序O(n2)O(n)O(n2)O(1)希尔排序-O(1)起泡排序O(n2)O(n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)简单选择排序O(n2)O(n2)O(n2)O(1)堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)归并排序O(nlog2n)-O(n)基数排序O(d(n+rd)O(d(n+rd)O(d(n+rd)O(rd)说明：说明：1.简洁排序：指全部时间困难度为简洁排序：指全部时间困难度为O(n2)的排序方法，包括干脆插入的排序方法，包括干脆插入排序、起泡排序、简洁选择排序。排序、起泡排序、简洁选择排序。2.从平均时间性能来说，快速排序最佳，其所需时间最省，但在最坏从平均时间性能来说，快速排序最佳，其所需时间最省，但在最坏状况下（基本有序状况下（基本有序/有序）的时间性能不如归并排序和堆排序。有序）的时间性能不如归并排序和堆排序。3.而对于归并排序和堆排序来说，在而对于归并排序和堆排序来说，在n较大时，归并排序所需时间较大时，归并排序所需时间较堆排序省，但这是以须要的协助空间多为代价较堆排序省，但这是以须要的协助空间多为代价排序方法平均时间最好情况最坏情况辅助空间直接插入排序O(n2)O(n)O(n2)O(1)希尔排序-O(1)起泡排序O(n2)O(n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)简单选择排序O(n2)O(n2)O(n2)O(1)堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)归并排序O(nlog2n)-O(n)基数排序O(d(n+rd)O(d(n+rd)O(d(n+rd)O(rd)从稳定性的角度来看：从稳定性的角度来看：不稳定的算法有：简洁选择排序、希尔派序、快速不稳定的算法有：简洁选择排序、希尔派序、快速排序、堆排序排序、堆排序导致不稳定的主要因素：比较或交换时不是在相邻导致不稳定的主要因素：比较或交换时不是在相邻的两个记录之间进行。的两个记录之间进行。小结：v各种排序方法的原理和过程v时间困难度、空间困难度v稳定性 假如在排序前，关键字序列已接近正序，则在干脆插入假如在排序前，关键字序列已接近正序，则在干脆插入排序和快速排序两者之中，选用排序和快速排序两者之中，选用_ _ _较为适当。较为适当。