第9章内排序2

1、1主要内容29.1 9.1 排序的基本概念排序的基本概念9.2 9.2 插入排序插入排序9.3 9.3 交换排序交换排序9.4 9.4 选择排序选择排序9.5 9.5 归并排序归并排序9.6 9.6 分配排序分配排序9.7 9.7 性能比较性能比较 选择排序的主要操作是选择，其主要思想是：每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。 有序序列有序序列1 12 2i i-1-1i in nk k无序序列无序序列n ni+i+1 11 12 2i i-1-1i ii i交换交换最小记录最小记录9.4 9.4 选择排序选择排序常用的选择排序算法：常用的选择排序算法： （1 1）

2、直接选择排序）直接选择排序 （2 2）堆排序）堆排序39.4.1 9.4.1 直接选择排序直接选择排序41 1、基本思想、基本思想 每经过一趟比较就找出一个最小值，与待排序列最前面的每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换位置互换. . 2 2、优点：、优点：实现简单实现简单3 3、缺点：、缺点：每趟只能确定一个元素，表长为每趟只能确定一个元素，表长为n n时需要时需要n-1n-1趟趟 4 4、前提：、前提：顺序存储结构顺序存储结构 9.4 9.4 选择排序选择排序50 1 2 3 4 5最小者最小者5、直接选择排序的过程直接选择排序的过程9.4.1 9.4.1 直接选择排序

3、直接选择排序6最小者最小者0 1 2 3 4 5结果结果各趟排序后的结果各趟排序后的结果9.4.1 9.4.1 直接选择排序直接选择排序解决方法：解决方法： 设置一个整型变量设置一个整型变量indexindex，用于记录在一趟比较的用于记录在一趟比较的过程中关键码最小的记录位置。过程中关键码最小的记录位置。 如何在无序区中记录关键码最小的记录？如何在无序区中记录关键码最小的记录？indexindexindexindex indexindex需解决的关键问题需解决的关键问题? ?79.4.1 9.4.1 直接选择排序直接选择排序解决方法： 第i趟简单选择排序的待排序区间是ri rn，则ri是无序

4、区第一个记录，所以，将index所记载的关键码最小的记录与ri交换。如何确定最小记录交换后的最终位置？如何确定最小记录交换后的最终位置？需解决的关键问题需解决的关键问题? ?89.4.1 9.4.1 直接选择排序直接选择排序97、直接选择排序的算法直接选择排序的算法void SelectSort ( elemtype L,int n ) for ( i = 1; i n; i+ ) /*总共进行n-1次排序*/ k = i; for ( j = i+1; j n; j+) /*在剩余记录序列中选择最小的记录*/ if ( rj =1; i-); i=1; i-) HeapAdjust(r, i

5、, n) HeapAdjust(r, i, n) ;/;/将序列将序列rinrin建成堆建成堆 关键问题关键问题1 1：如何新建堆？如何新建堆？189.4.2 9.4.2 堆排序堆排序关键问题关键问题2 2：如何处理堆顶记录？：如何处理堆顶记录？49 25 21 25* 16 081 2 3 4 5 6对对应应交换交换08 25 21 25* 16 491 2 3 4 5 6对对应应123456123456199.4.2 9.4.2 堆排序堆排序算法描述：算法描述： r1rn-i+1; r1rn-i+1; 解决方法：解决方法： 第第 i i 次处理堆顶是将堆顶记录次处理堆顶是将堆顶记录r1r1

6、与序列中第与序列中第n-i+1n-i+1个记录个记录rn-i+1rn-i+1交换。交换。关键问题关键问题2 2：如何处理堆顶记录？：如何处理堆顶记录？209.4.2 9.4.2 堆排序堆排序关键问题关键问题3 3：怎样将剩余记录调整成一个新堆？怎样将剩余记录调整成一个新堆？21* *算法描述：算法描述：HeapAdjust(r, 1, n-i);解决方法：解决方法： 第第 i 次调整剩余记录，此时，剩余记录有次调整剩余记录，此时，剩余记录有n-i个，个，调整根结点至第调整根结点至第n-i个记录。个记录。9.4.2 9.4.2 堆排序堆排序例:对刚才建好的大根堆进行排序：22交换交换 1号与号与

7、 6 号记录号记录 r1 rn492525*21160812345649 25 21 25* 16 08初始最大堆初始最大堆1365429.4.2 9.4.2 堆排序堆排序2316 25* 21 08 25 49交换交换 1号与号与 5 号记录号记录从从 1 号到号到 5 号号 重新重新调整为最大堆调整为最大堆082525*21164912345613654225 25* 21 08 16 499.4.2 9.4.2 堆排序堆排序24交换交换 1 号与号与 4 号记录号记录从从 1号到号到 4号号 重新重新调整为最大堆调整为最大堆1234561365429.4.2 9.4.2 堆排序堆排序25

8、08 16 21 25* 25 49交换交换 1号与号与3 号记录号记录从从 1 号到号到 3号号 重新重新调整为最大堆调整为最大堆1234561365429.4.2 9.4.2 堆排序堆排序2608 16 21 25* 25 49交换交换 1 号与号与2 号记录号记录排序完毕。排序完毕。从从 1 号到号到 2 号号 重新重新调整为最大堆调整为最大堆1234561365429.4.2 9.4.2 堆排序堆排序void HeapSort(elemtype h,int n) / /* * 对顺序表对顺序表* *h h进行堆排序进行堆排序 * */ / for(i=n/2；i=1；i-) Heapa

9、djust(h，i，n)； for(i=n；i=2；i-) temp=h1; h1=hi； hi=temp; /* HeapSort */ 27/ /* *将将hi.nhi.n建成大顶堆建成大顶堆 * */ / /* * 堆顶与堆底元素交换堆顶与堆底元素交换 * */ / /* *对对h1.i-1h1.i-1重新调整为堆重新调整为堆* */ /Heapadjust(h，1，i-1)；堆排序算法堆排序算法9.4.2 9.4.2 堆排序堆排序28void Heapajust(elemtype r，int s，int m) /* 对rs进行调整使其成为大顶堆 */ temp=rs；child=2*s

10、；/*temp暂存rs值，child是其左孩子*/ while(child=m) /*检查是否到达当前堆尾，未到尾则整理*/ if(childm&rchild=rchild) break;/*根大则不必调整，函数结束*/ else /*否则子女中的大者上移*/ s=child； /*将根下降到子女位置并继续向下整理！*/ rs=temp； /直到自下而上都满足堆定义，再放置入口结点针对结点针对结点 s 的堆调整函数的堆调整函数HeapAdjust ： 从结点从结点s开始到开始到当前堆尾当前堆尾m为止，自上向下比较，如果子女的为止，自上向下比较，如果子女的值大于双亲结点的值，则互相交换，

11、即把局部调整为大根堆。值大于双亲结点的值，则互相交换，即把局部调整为大根堆。rs=rchild；child=child*2;9.4.2 9.4.2 堆排序堆排序练习：练习：已知序列503，87，512，61，908，170，897，275，653，462，写出采用堆排序法对该序列作升序排列的第一趟结果。29第一趟结果：908,653,897,503,462,170,512,275,61,879.4.2 9.4.2 堆排序堆排序305、堆排序算法分析：、堆排序算法分析： 时间效率： O(nlog2n)。因为整个排序过程中需要调用n-1次堆顶点的调整，而每次堆排序算法本身耗时为log2n； 空间效

12、率：O(1)。仅在第二个for循环中交换记录时用到一个临时变量temp。 稳定性： 不稳定。 优点：对小文件效果不明显，但对大文件有效。9.4.2 9.4.2 堆排序堆排序主要内容319.1 9.1 排序的基本概念排序的基本概念9.2 9.2 插入排序插入排序9.3 9.3 交换排序交换排序9.4 9.4 选择排序选择排序9.5 9.5 归并排序归并排序9.6 9.6 分配排序分配排序9.7 9.7 性能比较性能比较9.5 9.5 归并排序归并排序321、基本思想：将若干有序序列逐步归并，最终得到一个有序序列。 （归并排序主要是二路归并排序）2、二路归并排序：可以把一个长度为n 的无序序列看成

13、是 n 个长度为 1 的有序子序列 ，首先做两两归并，得到 n / 2 个长度为 2 的有序子序列 ；再做两两归并，如此重复，直到最后得到一个长度为 n 的有序序列。需解决的关键问题需解决的关键问题?如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？怎样完成一趟归并？怎样完成一趟归并？如何控制二路归并的结束？如何控制二路归并的结束？33212525* 936272083716544921 2525* 4962 9308 7216 375416 37 5421 25 25* 4908 62 72 9308 21 25 25* 49 62 72 9308 16 21 25 2

14、5* 37 49 54 62 72 93len=1len=2len=4len=8len=1616 37 54整个归并排序仅需整个归并排序仅需 log2n 趟趟关键问题：关键问题：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j609.5 9.5 归并排序归并排序34kkk在归并过程中，可能会破坏原在归并过程中，可能会破坏原来的有序序列，所以，将归并来的有序序列，所以，将归并的结果存入另外一个数组中。的结果存入另外一个数组中。 关键问题：关键问题：如何将

15、两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j609.5 9.5 归并排序归并排序3536算法思想（以升序为例）：先用两个指针分别指向两个序列的第一个数据元素，进行比较，取出较小者，然后将其所在序列的指针后移，重复以上过程，直到指针达到序列的末尾，这时将另一个序列的剩余元素依次顺序放到有序序列的后面即可。关键问题：关键问题：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？s m m+1 t r s t r1 ijk9.5 9.5 归

16、并排序归并排序37具体步骤：将两个有序序列rs.m和rm+1.t归并为有序序列r1s.t的过程： i=s；j=m+1；k=s； 若im 或 jt，执行(4)； 比较ri和rj关键字,将较小的存入r1中: 如果ri rj； r1k=ri；i+； k+；执行； 否则，r1k=rj; j+; k+;执行； 将尚未处理完的子表中元素存入r1； 如果i=m，将rim存入r1kt； 如果j=t，将rjt存入r1kt； 合并结束。9.5 9.5 归并排序归并排序void Merge (int r , int r1 , int s, int m, int t ) i=s; j=m+1; k=s; while

17、(i=m & j=t) if (ri=rj) else while (i=m) /收尾处理收尾处理 r1k+=ri+; /前一个子序列前一个子序列 while (j=t) r1k+=rj+; /后一个子序列后一个子序列 算法描述：算法描述：r1k=ri；i+；k+; r1k=rj；j+；k+;9.5 9.5 归并排序归并排序38关键问题：关键问题：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？602031544556520 605 3144 5565 60 20 31 5 44 55 65ij5kj20i31j60子序列的长度一定相等吗子序列的长度一定相等吗?

18、9.5 9.5 归并排序归并排序39关键问题：关键问题：怎样完成一趟归并？怎样完成一趟归并？602031544556520 605 3144 556560 20 31 5 44 55 65 5 20 31 60 44 55 65在一趟归并中，除最后一个有序序列外，其它有序在一趟归并中，除最后一个有序序列外，其它有序序列中记录的个数相同，用长度序列中记录的个数相同，用长度h表示。表示。9.5 9.5 归并排序归并排序40关键问题：关键问题：怎样完成一趟归并？怎样完成一趟归并？现在的任务是把若干个长度为现在的任务是把若干个长度为h的有序序列和最后一个长的有序序列和最后一个长度有可能小于度有可能小于

19、h的有序序列归并，设的有序序列归并，设i指向待归并序列的指向待归并序列的第一个记录，有三种情况：第一个记录，有三种情况：若若in-2h+1，则相邻两个有序表的长度均为则相邻两个有序表的长度均为h，执行执行一次归并，完成后一次归并，完成后i加加2h，准备进行下一次归并；准备进行下一次归并；20 605 3144 5565 70ihi=1n-2h+1=5n-2h+1算法描述：算法描述：while (in-2h+1) Merge (r, r1, i, i+h-1, i+2*h-1); i+=2*h;9.5 9.5 归并排序归并排序41若若in-h+1，则表示仍有两个相邻有序表，一个长则表示仍有两个相

20、邻有序表，一个长度为度为h，另一个长度小于另一个长度小于h，则执行两个有序表的归并，则执行两个有序表的归并，完成后退出一趟归并。完成后退出一趟归并。20 605 3144 5565ihi=5n-2h+1=4n-h+1=6n-2h+1n-h+1=n-h+1) for (k=i; k=n; k+) r1k=rk; 9.5 9.5 归并排序归并排序43void MergePass (int r , int r1 , int n, int h)/对r做一趟归并，结果存入r1 i=1; while (in-2h+1) /长度均为h的区间合并 Merge (r, r1, i, i+h-1, i+2*h-1

21、); i+=2*h; if (in-h+1) /长度不相等的区间合并 Merge (r, r1, i, i+h-1, n); else for (k=i; k=n; k+) /只有一个区间 r1k=rk;一趟归并排序算法一趟归并排序算法9.5 9.5 归并排序归并排序44解决方法：解决方法： 开始时，有序序列的长度开始时，有序序列的长度h=1，结束时，有序序结束时，有序序列的长度列的长度h=n，用有序序列的长度来控制排序的结束。用有序序列的长度来控制排序的结束。关键问题：关键问题：如何控制二路归并的结束？如何控制二路归并的结束？9.5 9.5 归并排序归并排序45算法描述：void Merge

22、Sort (int r , int r1 , int n ) h=1; while (hn) MergePass (r, r1, n, h); /一次合并 h=2*h; /区间扩大 MergePass (r1, r, n, h); /再次合并 h=2*h; 关键问题：关键问题：如何控制二路归并的结束？如何控制二路归并的结束？9.5 9.5 归并排序归并排序46二路归并排序算法的性能分析二路归并排序算法的性能分析时间性能：时间性能： 二路归并排序的时间复杂度等于归并趟数与每一趟时间复杂度的乘积。而归并趟数为log2n。每一趟归并就是将两两有序子区间合并成一个有序子区间，而每一对有序子区间归并时，

23、记录的比较次数均小于等于记录的移动次数，而记录的移动次数等于数组中记录的个数n，即每一趟归并的时间复杂度为O(n)。因此，二路归并排序的时间复杂度为O(nlog2n)。空间性能：空间性能： 算法在执行时，需要占用与原始记录序列同样数量的存储空间，因此空间复杂度为O(n)。稳定性：稳定性： 稳定9.5 9.5 归并排序归并排序47练习：一组记录的排序码为（25，48，16，35，79，82，23，40，36，72）,其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（ ）.48（16 25 35 48 23 40 79 82 36 72）9.5 9.5 归并排序归并排序

24、主要内容499.1 9.1 排序的基本概念排序的基本概念9.2 9.2 插入排序插入排序9.3 9.3 交换排序交换排序9.4 9.4 选择排序选择排序9.5 9.5 归并排序归并排序9.6 9.6 分配排序分配排序9.7 9.7 性能比较性能比较1. 1. 什么是什么是“多关键字多关键字”排序？实现方法？排序？实现方法？例1：对一副扑克牌该如何排序？ 若规定花色和面值的顺序关系为： 花色： 面值：2 3 4 5 6 7 8 9 10 J Q K A 可以先按花色排序，花色相同者再按面值排序； 也可以先按面值排序，面值相同者再按花色排序。多关键字排序的实现方法通常有两种： 最高位优先法MSD

25、(Most Significant Digit first) 最低位优先法LSD (Least Significant Digit first)509.6.1 9.6.1 多关键字排序多关键字排序51因为有分组，故此算法需递归实现。例：初始关键字序列T=（32, 13, 27, 32*, 19，33），请分别用MSD和LSD进行排序，并讨论其优缺点。法法1（MSD）：）：原始序列：32, 13, 27, 32*, 19， 33 先按高位Ki1 排序：（13, 19）, 27, （32, 32*，33） 再按低位Ki2 排序 ： 13, 19 ， 27, 32, 32*, 33法法2（LSD）：

26、）： 原始序列： 32, 13, 27, 32*, 19 ，33 先按低位Ki2排序： 32, 32*, 13, 33, 27, 19 再按高位Ki1排序： 13, 19 , 27, 32, 32*, 33无需分组，易编程实现！9.6.1 9.6.1 多关键字排序多关键字排序52 设n 个记录的序列为：V0, V1, , Vn-1 ，可以把每个记录Vi 的单关键码 Ki 看成是一个d元组（Ki1, Ki2, , Kid），则其中的每一个分量Kij ( 1 j d ) 也可看成是一个关键字。4注1： Ki1最高位，Kid最低位；Ki共有d位，可看成d元组；注2： 每个分量Kij (1 j d )

27、 有radix种取值，则称radix为基数。26(9, 8, 4)(0, 1, , 9)（a, b, , z）(d, i, a, n)310例1：关键码984可以看成是 元组；基数radix 为 。例2：关键码dian可以看成是 元组；基数radix 为 。u相关概念：9.6.1 9.6.1 多关键字排序多关键字排序53例：T=（02，77，70，54，64，21，55，11），用LSD排序。分析：各关键字可视为2元组；每位的取值范围是：0-9；即基数radix 10 。因此，特设置10个队列，并编号为0-9。1155216454707702原始序列12345678先对低位扫描出队012345

28、678910个队列1、计算机怎样实现LSD算法？分配过程收集过程下一步775564540211217012345678出队后序列775554，64217002，119.6.2 基数排序540123456789再次入队再次出队再对高位扫描小结：小结：排序时经过了反复的“分配”和“收集”过程。当对关键字所有的位进行扫描排序后，整个序列便从无序变为有序了。775564540211217012345678出队后序列706454211102再次分配再次收集7770645554211102再次出队后序列这种LSD排序方法称为：基数排序基数排序，77，55 基数排序不需要进行排序码的比较，它采用“分配”与“

29、收集”的办法，是一种借助多关键码排序的思想实现单关键字排序的方法。即：用关键字不同的位值进行排序。552、基数排序的基本思想9.6.2 基数排序563、基数排序算法的实现思路 设待排序的数据元素关键字是m位d进制整数（不足 m位的关键字在高位补0），设置d个队列，令其编号分别为0,1,2,d-1。（1）按关键字最低位的数值依次把各数据元素放到相应的队列中；（2）按照队列号从小到大和进入队列中数据元素的先后次序收集分配在各队列中的数据元素；这样，就形成了数据元素集合的一个新的排列，称这样的一次排序过程为一次基数排序。（3）再对得到的数据元素序列按关键字次低位的数值依次把各数据元素放到相应的队列中

30、，重复收集过程，当完成了第m次基数排序后，就得到了排好序的数据元素序列。9.6.2 基数排序57用链队列来实现基数排序链式基数排序实现思路：实现思路： 针对 d 元组中的每一位分量，把原始链表中的所有记录, 按Kij的取值， j = d, d-1, , 1， 先“分配”到radix个链队列中去； 然后再按各链队列的顺序，依次把记录从链队列中“收集”起来； 分别用这种“分配”、“收集”的运算逐趟进行排序； 在最后一趟“分配”、“收集” 完成后，所有记录就按其关键码的值从小到大排好序了。3、基数排序算法的实现思路9.6.2 基数排序 例：请实现以下关键字序列的链式基数排序：T=（614，738，9

31、21，485，637， 101，215，530，790，306）614921485637738101215530790306第一趟分配第一趟分配e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9原始序列静态链表：r0（从最低位 i = 3开始排序，f 是队首指针，e 为队尾指针）第一趟收集第一趟收集（让队尾指针ei 链接到下一非空队首指针fi+1 即可）530790921101614485215306637738r05859第一趟收集的结果：第一趟收集的结果：e0 e1

32、 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9第二趟分配第二趟分配（按次低位 i = 2 ）530790921101614485215306637738第二趟收集第二趟收集（让队尾指针ei 链接到下一非空队首指针fi+1 ）530790921101614485215306637738r0r060第二趟收集的结果：第二趟收集的结果：530790921101614485215306637738e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637

33、101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9第三趟分配（按最高位第三趟分配（按最高位 i = 1 ）第三趟收集第三趟收集（让队尾指针ei 链接到下一非空队首指针fi+1 ）530790921101614485215306637738r0r0排序结束！时间复杂度：时间复杂度：若每个关键码有d 位，需要重复执行d 趟“分配”与“收集”。每趟对 n 个对象进行“分配”，对radix个队列进行“收集”。总时间复杂度为O(d*n)。空间复杂度：空间复杂度：算法中需要d次使用n个结点临时存放n个数据元素，所以空间复杂度为O（n）。稳定性：稳定性：基数排序是稳定的排序方法。9.6.3 基数排序算法分析61主要内容629.1 9.1 排序的基本概念排序的基本概念9.2 9.2 插入排序插入排序9.3 9.