《数据结构》排序》PPT课件复习过程.ppt

《《数据结构》排序》PPT课件复习过程.ppt》由会员分享，可在线阅读，更多相关《《数据结构》排序》PPT课件复习过程.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第第9章章 排序排序9.1插入排序插入排序 9.2交换排序交换排序 9.3选择排序选择排序 9.4归并排序归并排序 习题习题经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用排序是针对记录的集合排序是针对记录的集合R1,R2,Rn，其相应的关键字，其相应的关键字序列为序列为K1,K2,Kn，重组记录之间的关系，使，重组记录之间的关系，使记录的记录的排列次序满足相应的排列次序满足相应的关键

2、字关键字的的递增递增或或递减递减关系。记录的集关系。记录的集合也称为待排序合也称为待排序序列序列。若待排序。若待排序序列序列完全存放完全存放在内存在内存中，中，则该排序称为则该排序称为内部排序内部排序；若由于；若由于数据数据集合太大，在排序过集合太大，在排序过程中，需对程中，需对外存外存进行访问，则该排序称为进行访问，则该排序称为外部排序外部排序。有如下一组待排序序列有如下一组待排序序列(每个记录只列出关键字一项每个记录只列出关键字一项)：53,25,67(1),46,29,67(2),89,43,67(3),76 括号括号里的里的数字数字代表等值记录的代表等值记录的位置位置，若排序后为：，若

3、排序后为：25,29,43,46,53,67(1),67(2),67(3),76,89 则称所用的则称所用的排序方法排序方法是是稳定稳定的，反之，若三个等值记录的的，反之，若三个等值记录的排列顺序不是上述顺序，就称所用排序的方法是不稳定的。排列顺序不是上述顺序，就称所用排序的方法是不稳定的。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用9.1 插入排序插入排序9.1.1 直接插入排序直接插入排序它的基本操作是在处理第i个记录时，前面1到i-1记录已排成有序，将第i个记录插入有序表中，得到一个新的有序表，表的长度

4、加1。当表中只有一个记录时，该表已是有序表，所以，可以从第二个记录开始，逐个插入记录，直至处理完待排序序列的所有记录。直接插入排序的时间复杂度为O(n2)，并且是一种稳定排序。当n较小时，排序的效率较高，是一种常用的排序方法经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用处理记录号插入位置下标0123456i=1j=091 673562297246i=2j=067913562297246i=3j=035679162297246i=4j=135626791297246i=5j=029356267917246i=6j

5、=429356267729146i=7j=229354662677291图9.1直接插入排序示例例如，有一组关键字序列为91,67,35,62,29,72,46，直接插入排序过程如图9.1所示。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用用C语言描述的直接插入排序算法如下：typedefstructintkey;/*其他域*/NODE;算法算法9.1直接插入排序算法。voidInsertSort(NODEarray,intn)/*对存放在数组array中，长度为n的序列排序*/inti,j;NODEx;for

6、(i=1;i=0&x.keyd2dt，并且当t1时，d1=1，该序列都可选作步长序列。一般采用步长序列为d1=n/2，di+1=di/2(n为待排序序列的长度)。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用用C语言描述的希尔排序算法如下：算法算法9.2希尔排序算法。voidShellSort(NODEarray,intn)/*对存放在数组array中，长度为n的序列希尔排序*/inti,j,step;NODEx;for(step=n/2;step0;step=step/2)/*step不断变小，直至为1*/f

7、or(i=step;i=0&x.keyarrayj.key)arrayj+step=arrayj;j=j-step;arrayj+step=x;希尔排序的分析是一个复杂的问题，但它的排序速度要比直接插入排序快，另外，它是一种不稳定排序经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用9.2 交换排序交换排序 交换排序基本思想：比较二个待排序记录的关键字，若为逆序，则交换位置，反之，保持原序。9.2.1 冒泡冒泡(简单交换排序简单交换排序)冒泡排序的方法是：首先比较arrayn-1.key和arrayn-2.key，

8、若为逆序则交换之，然后比较arrayn-2.key和arrayn-3.key，依此类推，直到比较array1.key和array0.key，称为一趟“冒泡”，其结果是将具有最小关键字的记录排到序列的第1个位置上。然后再arrayn-1到array1之间进行一趟“冒泡”，将具有次小关键字的记录排到序列的第2个位置上。依此类推，直到第n-1趟，在arrayn-1和arrayn-2之间进行“冒泡”后，待排序序列已排成有序。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用下一趟区间下标0123456初始关键字6，0916

9、73562297246第一趟冒泡后6，129916735624672第二趟冒泡后6，229359167466272第三趟冒泡后6，329354691676272第四趟冒泡后6，429354662916772第五趟冒泡后6，529354662679172第六趟冒泡后序列有序29354662677291图9.3冒泡排序示例例如，有一组关键字序列为91,67,35,62,29,72,46，冒泡排序过程如图9.3所示。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用用C语言描述的简单交换排序算法如下：算法算法9.3冒泡排

10、序算法。voidBubbleSort(NODEarray,intn)/*对存放在数组array中，长度为n的序列冒泡排序*/inti,j,flag;NODEtemp;for(i=0;ii;j-)/*从后向前比较，小数向前交换，最小值到前位*/if(arrayj.keyarrayj-1.key)temp=arrayj;arrayj=arrayj-1;arrayj-1=temp;flag=1;/*有逆序存在，flag为1*/if(flag=0)break;/*若一趟“冒泡”中没有逆序，则序列已有序*/冒泡排序的时间复杂度为O(n2)，并且是一种稳定排序。经营者提供商品或者服务有欺诈行为的，应当按照

11、消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用9.2.2 快速排序快速排序冒泡排序的一种改进。基本思想是：通过一趟排序后，大幅度减小排序序列的长度。在一趟排序后将某个记录根据其关键字，排到序列的中间位置，且左边所有记录的关键字都比它的关键字小，而右边所有记录的关键字都比它的关键字大，这样一趟排序后，不仅有一个记录已排到正确的位置上，如下标为i，而且待排序序列分裂成长度较小的两个待排序区间(array0到arrayi-1和arrayi+1到arrayn-1)，将上述过程称为“划分”。一次划分得到两个小序列，再递归地对这两个小序列进行划分，直到序列的长度为1

12、，这时待排序序列已排成有序。显然，一次划分的时间复杂度是O(n)，下面讨论划分的算法。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用对arraystart到arrayend序列进行划分，首先要确定一个划分标准，通常选取序列的第一个记录的关键字，用变量mid暂存，另附设两个指针i和j，其初值分别为start和end，划分的具体做法如下(i=start，j=end)：(1)j从所指的位置开始从后向前扫描，直到arrayj.key=end)return;/*仅有一个记录*/i=start;j=end;mid=arra

13、yi;while(ij)while(imid.key)j-;if(ij)arrayi=arrayj;i+;while(ij&arrayi.key=mid.key)i+;if(ij)arrayj=arrayi;j-;arrayi=mid;/*一趟划分结束*/Quick_Sort(array,start,i-1);/*对start到i-1的记录进行划分*/Quick_Sort(array,i+1,end);/*对i+1到end的记录进行划分*/平均时间复杂度为O(nlog2n)，最坏这时快速排序等同于冒泡排序，时间复杂度为O(n2)。快速排序是不稳定的排序。经营者提供商品或者服务有欺诈行为的，应当

14、按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用9.3 选择排序选择排序选择排序的基本思想是：每一趟在n-i+1(i=1,2,n-1)个记录中选关键字最小的记录作为有序序列中第i个记录。9.3.1 直接选择排序直接选择排序直接选择排序又称为简单选择排序，其算法是：对n个记录排序，依次选出n-1个极值，置于相应目标位置。对array0到arrayn-1排序，需进行n-1趟扫描，第i趟扫描是从arrayi到arrayn-1中，经过n-i次比较，选出关键字最小的元素，置于arrayi位置中。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受

15、到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用算法算法9.5直接选择排序算法。voidSelect_Sort(NODEarray,intn)/*对array中n个记录进行选择排序*/inti,j,min;NODEtemp;for(i=0;in-1;i+)min=i;/*设min为第i趟中最小关键值记录的下标*/for(j=i+1;jn;j+)if(arrayj.keyarraymin.key)min=j;/*找最小关键值的下标*/if(i!=min)temp=arrayi;arrayi=arraymin;arraymin=temp;直接选择排序算法的时间复杂度为O(n2)，它是

16、一个不稳定排序。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用9.3.2 树形选择排序树形选择排序(1)简单树形选择排序简单树形选择排序简单树形选择排序的方法是：首先对待排序序列中n个记录的关键字进行两两比较，将其中关键字较小的n/2个记录取出，然后将这n/2个关键字再进行两两比较，选择出具有较小关键字的记录，如此重复，直到选出一个最小关键字的记录。这个过程可用一棵有n个叶子结点的完全二叉树表示。有一组关键字序列为49,38,65,97,76,13,27,49，在这8个关键字中选出最小关键字的过程如图9.5(a

17、)所示。在输出最小关键字后，仅需将叶子结点中最小关键字(13)改为“最大值”，然后调整从树叶到根结点的路径上各结点的关键字，则根结点的关键字为次小关键字，如图9.5(b)所示。同理，可依次选出从小到大的所有关键字。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图9.5树形选择排序的示例时间复杂度:O(nlog2n)缺点:是占用较多的存储空间来保存比较结果。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用(2)堆排序堆排序堆的定义：

18、有n个记录的线性序列，其关键值序列为(k1,k2,kn)，满足如下条件：ki=k2i2i=k2i2i=nki=k2i+12i+1=2i+12i+1=n为在C语言中设计算法方便，修改堆定义为：若关键值序列为(k0,k1,kn-1)，满足如下条件：ki=k2i2i+1=nki=k2i+22i+2=n称之为堆。图9.6堆的示例一维数组看作是一棵完全二叉树的顺序存储形式。则堆是：完全二叉树中所有的非终端结点的关键字均不大于(或不小于)其左右孩子结点的关键字。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用若在输出堆顶具有

19、最小关键字值的记录之后，使得剩余n-1记录的序列重又建成一个堆，则得到n个记录中关键字次小值。如此反复执行，直到得到一个有序序列，这个过程称为堆排序。由此，实现堆排序需要解决两个问题：如何将一个待排序序列建成一个堆？如何在输出堆顶记录之后，调整剩余记录成一个新堆?关键字序列13,38,27,49,76,65,49,97是一个堆，如图9.7(a)所示，在输出堆顶记录之后，以堆中最后一个元素替代之，如图9.7(b)所示。此时，根结点的左、右子树均为堆，则仅需自上而下进行调整即可。首先以堆顶元素和其左、右子树根结点的较小值27比较，因堆顶元素97大，所以二者交换。交换之后又破坏右子树“堆”，则需要进

20、行和上述相同的调整，直至树叶(如图9.7(c)所示)或调整后子树的“堆”没有被破坏结束。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图9.7输出堆顶元素并调整建成新堆的过程称这个自堆顶至树叶的调整过程为“筛选”经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用现在讨论第一个问题，即将一个待排序序列建成一个堆的过程，该过程就是一个反复“筛选”的过程。此时将序列看成一个完全二叉树，并且树最后一个非终端结点是序列的第trunc(n/2)

21、个元素，在该元素开始到序列第一个元素的区间里，依次以每一个元素作为堆顶进行一次“筛选”，可将待排序序列建成一个堆。例如，有一组关键字序列为49,38,65,97,76,13,27,49，将这8个关键字建成一个堆的过程如图9.8所示。称这个自堆顶至树叶的调整过程为“筛选”经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图9.8将待排序列建成堆的过程经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用算法算法9.6 堆排序算法。voidhe

22、apshift(NODEarray,inti,intn)/*对以arrayi为顶的堆，进行筛选，n为待排序列长度*/NODEtemp=arrayi;intj=2*i+1;/*j为结点i左孩子的下标*/while(jn)if(j+1arrayj+1.key)j+;/*j为结点i左右孩子中较小者的下标*/if(temp.keyarrayj.key)arrayi=arrayj;i=j;j=2*i+1;elsebreak;/*筛选结束*/arrayi=temp;/*arrayi是temp应在的位置*/未完结下一页经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金

23、额为消费者购买商品的价款或接受服务的费用voidheapsort(NODEarray,intn)/*对存放在array中，长度为n的序列进行对排序*/inti;NODEtemp;for(i=n/2-1;i=0;i-)heapshift(array,i,n);/*以每一个非终端结点为堆顶，筛选建立堆*/for(i=n-1;i0;i-)temp=array0;array0=ai;ai=temp;/*将最小值交换至数组末尾*/*从array0开始在array0到arrayi-1之间筛选*/heapshift(a,0,i);堆排序的时间复杂度O(nlog2n)，它是一种不稳定的排序方法。经营者提供商品

24、或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用9.4 归并排序归并排序 归并是将两个有序序列归并为一个有序序列。归并是将两个有序序列归并为一个有序序列。将将2-路归并的思想用于有路归并的思想用于有n个记录的待排序列中，个记录的待排序列中，就得到归并排序。首先，把就得到归并排序。首先，把n个记录看成是长度个记录看成是长度为为1有序表，将它们两两归并，得到长度为有序表，将它们两两归并，得到长度为2的若

25、的若干个有序子表，重复上述过程，直到得到长度为干个有序子表，重复上述过程，直到得到长度为n的有序表为止。的有序表为止。例如，有一组关键字序列为例如，有一组关键字序列为 49,38,65,97,76,13,27对这对这7个关键字进行归并排序的过程如图个关键字进行归并排序的过程如图9.9所示。所示。经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用下标0123456初始关键字49386597761327-一趟归并之后38496597761327-二趟归并之后38496597132776-三趟归并之后13173849657697图9.92-路归并排序的示例归并排序的时间复杂度为O(log2n)，是一种稳定的排序方法，但该算法所占用空间较大，需要一个与待排序列相同的辅助空间。具体算法由读者根据两个有序序列归并算法，即“平移指针，一次扫描”的算法，自己完成。