第十章内部排序4选择排序5归并排序6基数排序课件.ppt

1、数据结构 10.1 概述概述第十章第十章 内部排序内部排序 10.2 插入排序插入排序 10.3 快速排序快速排序 10.4 选择排序选择排序 10.5 归并排序归并排序 10.6 基数排序基数排序 10.7 各种内部排序方法的比较各种内部排序方法的比较基本思想：基本思想：每一趟在每一趟在n-i+1(i=1,2,n)个记录中选取关键个记录中选取关键字最小的记录作为有序序列中的第字最小的记录作为有序序列中的第i个记录。个记录。10.4 选择排序选择排序有序序列有序序列12i-1ink无序序列无序序列ni+112i-1ii交换交换最小记录最小记录u简单选择排序简单选择排序u树形选择排序树形选择排序

2、u堆排序堆排序思路：思路：一一.简单选择排序简单选择排序 10.4 选择排序选择排序 每次经每次经 n-i 次比较，从次比较，从 n-i+1个记录中选出个记录中选出第第 i 小的记录，并与第小的记录，并与第 i 位置记录交换。位置记录交换。初始关键字初始关键字49 38 65 97 76 13 27 49i=1i=113 38 65 97 76 49 27 49例例i=2i=213 27 65 97 76 49 38 49i=3i=313 27 38 97 76 49 65 49i=4i=413 27 38 49 76 97 65 49i=5i=513 27 38 49 49 97 65 76

3、i=6i=613 27 38 49 49 65 97 76i=7i=713 27 38 49 49 65 76 97 每次经每次经 n-i 次比较，从次比较，从 n-i+1个记录中选出个记录中选出第第 i 小的记录，并与第小的记录，并与第 i 位置记录交换。位置记录交换。思路：思路：10.4 选择排序选择排序解决方法：解决方法：设置一个整型变量设置一个整型变量index，用于记录在一趟比较的，用于记录在一趟比较的过程中关键码最小的记录位置。过程中关键码最小的记录位置。indexindex index关键问题关键问题:如何在无序区中选出关键码最小的记录？如何在无序区中选出关键码最小的记录？10.

4、4 选择排序选择排序关键问题关键问题:如何在无序区中选出关键码最小的记录？如何在无序区中选出关键码最小的记录？indexindex算法描述：算法描述：index=i;for(j=i+1;j=L.length;j+)if(L.(L.rj.keyL.rindex.key)index=j;解决方法：解决方法：第第i趟简单选择排序的待排序区间是趟简单选择排序的待排序区间是ri rn，则，则ri是无序区第一个记录，所以，将是无序区第一个记录，所以，将index所记载的关所记载的关键码最小的记录与键码最小的记录与ri交换。交换。算法描述：算法描述：if(index!=i)L.riL.rindex;10.4

5、 选择排序选择排序关键问题关键问题：如何确定最小记录的最终位置？如何确定最小记录的最终位置？void SelectSort(SqList&L)for(i=1;iL.length;+i)index=i;for(j=i+1;j=L.length;j+)if(L.rj.keyL.rindex.key)index=j;/在在r i.L.length中选择中选择key最小的记录最小的记录 if(index!=i)L.ri L.rindex;/与第与第 i 记录交换记录交换 算法：算法：特点：特点：1)1)时间复杂度为时间复杂度为O(nO(n2 2)2)2)算法稳定算法稳定 改进的着眼点：改进的着眼点：如

6、何如何减少减少关键码间的关键码间的比较比较次数。次数。若能利用每趟比较后的结果，也就是在找出键值最若能利用每趟比较后的结果，也就是在找出键值最小记录的同时，也找出键值较小的记录，则可减少小记录的同时，也找出键值较小的记录，则可减少后面的选择中所用的比较次数，从而提高整个排序后面的选择中所用的比较次数，从而提高整个排序过程的效率。过程的效率。减少关键码间的比较次数减少关键码间的比较次数查找最小值的同时，找出较小值查找最小值的同时，找出较小值 10.4 选择排序选择排序ZHAOCHALIUBAODIAOYANGXUEWANGCHABAODIAOWANGBAODIAOBAO锦标赛过程示意图锦标赛过程

7、示意图冠军冠军1234567ZHAOCHALIUBAODIAOYANGXUEWANGCHALIUDIAOWANGCHADIAOCHA锦标赛过程示意图锦标赛过程示意图亚军亚军89ZHAOCHALIUBAODIAOYANGXUEWANGZHAOLIUDIAOWANGLIUDIAODIAO锦标赛过程示意图锦标赛过程示意图季军季军1011思路：思路：二二.树型选择排序树型选择排序 10.4 选择排序选择排序 以初始序列作为完全二叉树的叶子结点，从最后以初始序列作为完全二叉树的叶子结点，从最后的分支结点开始，选左右孩子中较小的的分支结点开始，选左右孩子中较小的(胜者胜者)为其双为其双亲的值，亲的值，相等

8、则取左孩子，直至选出树根，得到最小相等则取左孩子，直至选出树根，得到最小元素；元素；然后将此时根对应的叶子结点关键字值改为然后将此时根对应的叶子结点关键字值改为 最大值最大值，从该叶子起与兄弟比，较小的作为新的双亲，从该叶子起与兄弟比，较小的作为新的双亲，直至根，得到次小值直至根，得到次小值，依次可选出其余元素。，依次可选出其余元素。1313 4949 3838 3838 3838 6565 6565 9797 7676 131313131313 2727 2727 4949例：例：49 38 65 97 76 13 27 49 38 65 97 76 13 27 4949二二.树型选择排序树

9、型选择排序 10.4 选择排序选择排序 以初始序列作为完全二叉树的以初始序列作为完全二叉树的叶子结点，从最后的分支结点开始，叶子结点，从最后的分支结点开始，选左右孩子中较小的选左右孩子中较小的(胜者胜者)为其双为其双亲的值，亲的值，相等则取左孩子，直至选相等则取左孩子，直至选出树根，得到最小元素；出树根，得到最小元素；2727 4949 3838 3838 3838 6565 6565 9797 7676 2727 7676 2727 2727 4949二二.树型选择排序树型选择排序 10.4 选择排序选择排序例：例：49 38 65 97 76 13 27 49 38 65 97 76 13

10、 27 49491313 49 49 38 38 3838 3838 6565 65 65 97 977676131313131313 2727 27 27 4949然后将此时根对应的叶子结点关键字然后将此时根对应的叶子结点关键字值改为值改为 最大值最大值，从该叶子起与兄弟比，从该叶子起与兄弟比，较小的作为新的双亲，直至根，得到较小的作为新的双亲，直至根，得到次小值次小值，依次可选出其余元素。，依次可选出其余元素。缺点缺点：需增加额外空间来：需增加额外空间来存放中间比较结果和排序存放中间比较结果和排序结果，且算法实现困难。结果，且算法实现困难。三三.堆排序堆排序 堆的概念：堆的概念：堆堆是满足

11、下列性质的数列是满足下列性质的数列k1,k2,kn:kik2ikik2i+1kik2ikik2i+1或或 若上述数列是若上述数列是堆堆，则，则k1必是数列中的最小值或最大必是数列中的最小值或最大值，则称分别满足上式的序列为值，则称分别满足上式的序列为小顶堆小顶堆或或大顶堆大顶堆。完全二叉树中所有非终端结点的值均不大于完全二叉树中所有非终端结点的值均不大于（或不小于）其左右孩子的结点的值。（或不小于）其左右孩子的结点的值。10.4 选择排序选择排序如如堆堆9696，8383，2727，3838，1111，0909堆堆1212，3636，2424，8585，4747，3030，5353，91919

12、68327381109大顶堆大顶堆1236244785533091小顶堆小顶堆三三.堆排序堆排序 10.4 选择排序选择排序堆和序列的关系堆和序列的关系将堆用顺序存储结构来存储，则堆对应一组序列。将堆用顺序存储结构来存储，则堆对应一组序列。5038454028363220182850 38 45 32 36 40 28 20 18 281 2 3 4 5 6 7 8 9 10采用顺序存储采用顺序存储 10.4 选择排序选择排序三三.堆排序堆排序 堆排序的概念：堆排序的概念：在输出堆顶元素后，使得剩余的在输出堆顶元素后，使得剩余的n-1个元素重又个元素重又形成堆，以便再次输出新的堆顶元素。如此反

13、复执形成堆，以便再次输出新的堆顶元素。如此反复执行，最终形成一个有序序列的过程称为堆排序。行，最终形成一个有序序列的过程称为堆排序。10.4 选择排序选择排序ni+112i-1ii无序区无序区为一个堆为一个堆有序区有序区已经位于最终位置已经位于最终位置关键问题关键问题：如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？282516321836163216282518362532162818362528323628161825解决方法：解决方法：由一个无序由一个无序序列建堆的过程就是反序列建堆的过程就是反复复“筛选筛选”的过程。假的过程。假设最后一个结点（叶子）设最后一个结点（叶子）的

14、序号是的序号是n，则最后一个，则最后一个分支结点即为结点分支结点即为结点n的双的双亲，其序号是亲，其序号是n/2。“筛筛选选”即从即从第第n/2个元素个元素开开始。始。32362816182536 28 32 25 18 161 2 3 4 5 6对对应应交换交换16 28 32 25 18 361 2 3 4 5 6对对应应321628361825关键问题关键问题：如何处理堆顶记录？如何处理堆顶记录？解决方法：解决方法：第第 i 次处理堆次处理堆顶是将堆顶记顶是将堆顶记录录r1与序列中与序列中第第n-i+1个记录个记录rn-i+1交换。交换。关键问题关键问题:如何调整剩余记录成为一个新堆？如

15、何调整剩余记录成为一个新堆？32162836182516解决方法：解决方法：此时根结点的左右子树均为堆，只需调整此时根结点的左右子树均为堆，只需调整根结点，与其左右子树根结点中的较大或较小值交换，根结点，与其左右子树根结点中的较大或较小值交换，若交换后破坏了子树的若交换后破坏了子树的“堆堆”，则继续调整。，则继续调整。281632361825281618363225创建初始堆创建初始堆4938977649651327493897764965132749389776491365271338977649276549被筛选后建成的新堆被筛选后建成的新堆例：无序序列例：无序序列49,38,65,97,

16、76,13,27,49利用堆排序的利用堆排序的 方法进行降序排序方法进行降序排序建小顶堆。建小顶堆。输出堆顶元素，调整建新堆输出堆顶元素，调整建新堆1338977649276549973813764927654927381376494965979738137649496527384913769749652765497697493813276549769749654976974965499776659749769765769776657697形成降序序列：形成降序序列：97，76，65，49，49，38，27，1338132738132749 38132749 38132749 49 38132

17、749 49 38132765 49 49 381327特点：特点：堆排序适用于记录数较多的文件进行排序的情况。堆排序适用于记录数较多的文件进行排序的情况。堆排序为不稳定算法。堆排序为不稳定算法。三三.堆排序堆排序 10.4 选择排序选择排序 将两个或两个以上的有序表组合成一个新的有将两个或两个以上的有序表组合成一个新的有序表。即假设初始序列有序表。即假设初始序列有n个记录，可看成是个记录，可看成是n个个长度为长度为1的有序子序列，将其两两归并，得到的有序子序列，将其两两归并，得到n/2个个长度为长度为2或或1的有序子序列；再将其两两归并。如此的有序子序列；再将其两两归并。如此重复，直至得到一

18、个长度为重复，直至得到一个长度为n的有序序列为止。的有序序列为止。思路：思路：10.5 归并排序归并排序例例初始关键字初始关键字49 38 65 97 76 13 27 一趟归并后一趟归并后 38 49 65 97 13 76 27 二趟归并后二趟归并后 38 49 65 97 13 27 76 三趟归并后三趟归并后13 27 38 49 65 76 97 特点：特点：归并排序为稳定算法，但在一般情况下很少利归并排序为稳定算法，但在一般情况下很少利用用2 2路归并排序来操作，因其算法实用性较差。路归并排序来操作，因其算法实用性较差。2 2路归并排序算法路归并排序算法 10.6 基数排序基数排序

19、 基数排序是借助基数排序是借助多关键字排序多关键字排序的思想对单逻辑的思想对单逻辑关键字进行排序的方法。关键字进行排序的方法。例例 对对52张扑克牌按以下次序排序：张扑克牌按以下次序排序：2 3 A 2 3 A 2 3 A 2 3 A两个关键字：花色（两个关键字：花色（）面值（面值（23A）并且并且“花色花色”地位高于地位高于“面值面值”将逻辑关键字看成由将逻辑关键字看成由d个关键字复合而成，个关键字复合而成，每个关键字可能取每个关键字可能取r个值。则从最低位起，按关个值。则从最低位起，按关键字值将记录键字值将记录分配分配到到r个队列之后再个队列之后再收集收集到一起，到一起，如此重复如此重复d

20、趟，最终完成整个记录序列的排列。趟，最终完成整个记录序列的排列。基数指的是基数指的是r的取值范围的取值范围。思路：思路：10.6 基数排序基数排序 基数排序是借助多关键字排序的思想对单逻辑基数排序是借助多关键字排序的思想对单逻辑关键字进行排序的方法。关键字进行排序的方法。初始关键字初始关键字例例78 09 63 30 74 89 94 25 05 69 18 83第一趟分配第一趟分配3063837494250578180989690 1 2 3 4 5 6 7 8 9 10 110 1 2 3 4 5 6 7 8 9第一趟收集第一趟收集 30 63 83 74 94 25 05 78 18 0

21、9 89 690 1 2 3 4 5 6 7 8 9 10 11第二趟分配第二趟分配050918 25 30636974788389940 1 2 3 4 5 6 7 8 9第二趟收集第二趟收集 05 09 18 25 30 63 69 74 78 83 89 940 1 2 3 4 5 6 7 8 9 10 11针对个位数针对个位数针对十位数针对十位数特点：特点：适用于记录数多，但关键字较小的序列。适用于记录数多，但关键字较小的序列。基数排序为稳定算法。基数排序为稳定算法。10.6 基数排序基数排序10.7 各种内部排序算法比较各种内部排序算法比较方法方法 平均时间平均时间 最坏情况最坏情况

22、 辅助存储辅助存储 稳定稳定 备备 注注直接插入直接插入 n2 n2 1 o 起泡排序起泡排序 n2 n2 1 o 简单选择简单选择 n2 n2 1 o希尔希尔 n3/2 n3/2 1 x 快速快速 n*log n n2 log n x 树形选择树形选择 n*log n n*log n n x 堆排序堆排序 n*log n n*log n 1 x 归并归并 n*log n n*log n n o基数基数 d*(n+rd)d*(n+rd)rd o备注中标有备注中标有 的方法其时间复杂度与原始序列有关。的方法其时间复杂度与原始序列有关。待排记录数待排记录数n。一条记录所带信息量的大小。一条记录所带

23、信息量的大小。对排序稳定性的要求。对排序稳定性的要求。关键字的分布情况。关键字的分布情况。算法的时间复杂度和空间复杂度。算法的时间复杂度和空间复杂度。选择排序方法时需要考虑以下几个因素：选择排序方法时需要考虑以下几个因素：10.7 各种内部排序算法比较各种内部排序算法比较 1.已知数据序列为已知数据序列为(12，5，9，20，6，31，24)，对该数据序列进行排序，写出简单选择排序、对该数据序列进行排序，写出简单选择排序、堆排序、二路归并排序每趟的结果。堆排序、二路归并排序每趟的结果。2.设要将序列（设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列，则：中的关键码按字母序的升序重新排列，则：二路归并排序一趟扫描的结果是二路归并排序一趟扫描的结果是 ；堆排序；堆排序初始建小顶堆的结果是初始建小顶堆的结果是 。