第8章-排序要点.ppt

第八章第八章 排序排序DS应用实践应用实践插入排序插入排序 基数排序基数排序归并排序归并排序交换排序交换排序选择排序选择排序Hot Tip 本章学习的要点主要是了解各种排序方法实现时所依据的原则以及它们的主要操作（关键字间的比较和记录的移动）的时间分析。学习中应注意掌握各种排序方法实现的要点，切实掌握各种排序过程的排序特点所在。8.1基本概念基本概念v排序排序(Sorting)定义：是将一个数据元素（或定义：是将一个数据元素（或记记录）录）的任意序列，重新排列成一个按的任意序列，重新排列成一个按关键字关键字有序的序列。有序的序列。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具体步骤具体步骤 假假设设待待排排序序的的记记录录为为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;/有数据交换，循环继续有数据交换，循环继续算法评价算法评价时间复杂度时间复杂度最好情况（正序）最好情况（正序）Y比较次数：比较次数：n-1Y移动次数：移动次数：012345最坏情况（逆序）最坏情况（逆序）Y比较次数：比较次数：Y移动次数：移动次数：空间复杂度：空间复杂度：S(n)=O(1)T(n)=O(n)54321v冒泡排序比较简单，当初始序列基本有序时，冒泡冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效率，反之效率较低；其次冒泡排序排序有较高的效率，反之效率较低；其次冒泡排序只需要一个记录的辅助空间，用来作为记录交换的只需要一个记录的辅助空间，用来作为记录交换的中间暂存单元；中间暂存单元；冒泡排序是一种稳定的排序方法冒泡排序是一种稳定的排序方法。v冒泡排序时间复杂度的分析冒泡排序时间复杂度的分析：当最好的情况时，也：当最好的情况时，也就是要排序的表本身就是有序的，时间复杂度为就是要排序的表本身就是有序的，时间复杂度为O(n)。当最坏的情况时，即待排序表是逆序的情况，。当最坏的情况时，即待排序表是逆序的情况，此时需要比较此时需要比较次，并作次，并作等数量级的记录移动。因此，总的时间复杂度为等数量级的记录移动。因此，总的时间复杂度为O(n2)。8.3.2快速排序快速排序（划分交换排序）（划分交换排序）基本思想：在当前无序区基本思想：在当前无序区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时间复复杂度：度：一一般般情情况况(每每次次等等分分子子表表):):O(nlog(nlog2 2n)n)最坏情况（初始序列有序）：最坏情况（初始序列有序）：O(n(n2 2)p空空间性能：性能：1个个辅助空助空间。8.4选择排序选择排序v基本思想：每一趟在n-i+1(i=1,2,n)个记录中选取关键字最小的记录作有序序列中的第i个记录v直接选择排序首先通过首先通过n-1次关键字比较，从无序区次关键字比较，从无序区R1n中找中找出关键字最小的记录，将它与第一个记录交换出关键字最小的记录，将它与第一个记录交换再通过再通过n-2次比较，从无序区次比较，从无序区R2n中找出关键字中找出关键字次小的记录，将它与第二个记录交换次小的记录，将它与第二个记录交换重复上述操作，共进行重复上述操作，共进行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算法评价算法评价时间复杂度时间复杂度记录移动次数记录移动次数空间复杂度：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第一个问题解决方法第一个问题解决方法方法：从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选例例含含8个元素的无序序列（个元素的无序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133827657650971327384965765097v第二个问题解决方法第二个问题解决方法筛选筛选 方法：方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”例例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）并且“花色”地位高于“面值”8.6.1多关键字排序 一般情况下，假设有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链式基数排序步骤（对十进制数而言）设置10个队列，fi和ei分别为第i个队列的头指针和尾指针第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同8.6.2 链式基数排序第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列例例初始状态初始状态278109063930589184505269008083109278063930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配尾指针尾指针头指针头指针初始状态初始状态278109063930589184505269008083109278063930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配尾指针尾指针头指针头指针589184505初始状态初始状态278109063930589184505269008083109278063930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配尾指针尾指针头指针头指针589184505269初始状态初始状态278109063930589184505269008083109278063930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配尾指针尾指针头指针头指针589184505269008083930063083184505278008109589269一趟收集：一趟收集：505008109930063269278083184589二趟收集：二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二二趟趟分分配配008109278930063083184505278008109589269一趟收集的结果：一趟收集的结果：008063083109184269278505589930三趟收集：三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三三趟趟分分配配063083269278505589505008109930063269278083184589二趟收集的结果：二趟收集的结果：v算法评价时间复杂度时间复杂度：分配：分配：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稳定性 如果在排序前，关键字序列已接近正序，则在直接插入如果在排序前，关键字序列已接近正序，则在直接插入排序和快速排序两者之中，选用排序和快速排序两者之中，选用_较为适当。较为适当。