内部排序4选择排序5归并排序6基数排序.ppt

数据结构,10.1 概述,第十章 内部排序,10.2 插入排序,10.3 快速排序,10.4 选择排序,10.5 归并排序,10.6 基数排序,10.7 各种内部排序方法的比较,基本思想：,每一趟在n-i+1(i=1,2,n)个记录中选取关键字最小的记录作为有序序列中的第i个记录。,10.4 选择排序,简单选择排序 树形选择排序 堆排序,思路：,一.简单选择排序,10.4 选择排序,每次经 n-i 次比较，从 n-i+1个记录中选出第 i 小的记录，并与第 i 位置记录交换。,初始关键字,49 38 65 97 76 13 27 49,例,每次经 n-i 次比较，从 n-i+1个记录中选出第 i 小的记录，并与第 i 位置记录交换。,思路：,10.4 选择排序,解决方法： 设置一个整型变量index，用于记录在一趟比较的过程中关键码最小的记录位置。,21,28,25,16,49,08,index,index,08,关键问题:如何在无序区中选出关键码最小的记录？,10.4 选择排序,关键问题:如何在无序区中选出关键码最小的记录？,21,28,25,16,49,08,index,08,算法描述： index=i; for (j=i+1; j=L.length; j+) if (L.rj.keyL.rindex.key) index=j;,解决方法： 第i趟简单选择排序的待排序区间是ri rn，则ri是无序区第一个记录，所以，将index所记载的关键码最小的记录与ri交换。,算法描述： if (index!=i) L.riL.rindex;,10.4 选择排序,关键问题 ：如何确定最小记录的最终位置？,void SelectSort(SqList / 与第 i 记录交换 ,算法：,特点： 1) 时间复杂度为O(n2) 2) 算法稳定,改进的着眼点：如何减少关键码间的比较次数。若能利用每趟比较后的结果，也就是在找出键值最小记录的同时，也找出键值较小的记录，则可减少后面的选择中所用的比较次数，从而提高整个排序过程的效率。,减少关键码间的比较次数,查找最小值的同时，找出较小值,10.4 选择排序,锦标赛过程示意图,冠军,1,2,3,4,5,6,7,ZHAO,CHA,LIU,BAO,DIAO,YANG,XUE,WANG,CHA,LIU,DIAO,WANG,CHA,DIAO,CHA,锦标赛过程示意图,亚军,8,9,ZHAO,CHA,LIU,BAO,DIAO,YANG,XUE,WANG,ZHAO,LIU,DIAO,WANG,LIU,DIAO,DIAO,锦标赛过程示意图,季军,10,11,思路：,二.树型选择排序,10.4 选择排序,以初始序列作为完全二叉树的叶子结点，从最后的分支结点开始，选左右孩子中较小的(胜者)为其双亲的值， 相等则取左孩子，直至选出树根，得到最小元素； 然后将此时根对应的叶子结点关键字值改为 最大值，从该叶子起与兄弟比，较小的作为新的双亲，直至根，得到次小值 ，依次可选出其余元素。,例：49 38 65 97 76 13 27 49,二.树型选择排序,10.4 选择排序,以初始序列作为完全二叉树的叶子结点，从最后的分支结点开始，选左右孩子中较小的(胜者)为其双亲的值， 相等则取左孩子，直至选出树根，得到最小元素； ,二.树型选择排序,10.4 选择排序,例：49 38 65 97 76 13 27 49,然后将此时根对应的叶子结点关键字值改为 最大值，从该叶子起与兄弟比，较小的作为新的双亲，直至根，得到次小值 ，依次可选出其余元素。,缺点：需增加额外空间来 存放中间比较结果和排序 结果，且算法实现困难。,三.堆排序,堆的概念：,堆是满足下列性质的数列k1,k2,kn:,若上述数列是堆，则k1必是数列中的最小值或最大值，则称分别满足上式的序列为小顶堆或大顶堆。,完全二叉树中所有非终端结点的值均不大于（或不小于）其左右孩子的结点的值。,10.4 选择排序,如,堆96，83，27，38，11，09,堆12，36，24，85，47，30，53，91,三.堆排序,10.4 选择排序,堆和序列的关系,将堆用顺序存储结构来存储，则堆对应一组序列。,10.4 选择排序,三.堆排序,堆排序的概念：,在输出堆顶元素后，使得剩余的n-1个元素重又形成堆，以便再次输出新的堆顶元素。如此反复执行，最终形成一个有序序列的过程称为堆排序。,10.4 选择排序,无序区 为一个堆,有序区 已经位于最终位置,关键问题：如何由一个无序序列建成一个堆？,解决方法：由一个无序序列建堆的过程就是反复“筛选”的过程。假设最后一个结点（叶子）的序号是n，则最后一个分支结点即为结点n的双亲，其序号是n/2。“筛选”即从第n/2个元素开始。,对 应,对 应,关键问题 ：如何处理堆顶记录？,解决方法： 第 i 次处理堆顶是将堆顶记录r1与序列中第n-i+1个记录rn-i+1交换。,关键问题 :如何调整剩余记录成为一个新堆？,解决方法：此时根结点的左右子树均为堆，只需调整根结点，与其左右子树根结点中的较大或较小值交换，若交换后破坏了子树的“堆”，则继续调整。,创建初始堆,被筛选后建成的新堆,例：无序序列49,38,65,97,76,13,27,49利用堆排序的 方法进行降序排序建小顶堆。,输出堆顶元素，调整建新堆,13,38,97,76,49,27,65,49,97,38,13,76,49,27,65,49,27,38,13,76,49,49,65,97,97,38,13,76,49,49,65,27,38,49,13,76,97,49,65,27,65,49,76,97,49,38,13,27,65,49,76,97,49,65,49,76,97,49,65,49,97,76,65,97,49,76,97,65,76,97,76,65,76,97,形成降序序列： 97，76，65，49，49 ，38，27，13,38,13,27,38,13,27,49,38,13,27,49,38,13,27,49,49,38,13,27,49,49,38,13,27,65,49,49,38,13,27,特点：, 堆排序适用于记录数较多的文件进行排序的情况。 堆排序为不稳定算法。,三.堆排序,10.4 选择排序,将两个或两个以上的有序表组合成一个新的有序表。即假设初始序列有n个记录，可看成是n个长度为1的有序子序列，将其两两归并，得到n/2个长度为2或1的有序子序列；再将其两两归并。如此重复，直至得到一个长度为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路归并排序算法,10.6 基数排序,基数排序是借助多关键字排序的思想对单逻辑关键字进行排序的方法。,例 对52张扑克牌按以下次序排序： 23A23A 23A23A 两个关键字：花色（ ） 面值（23A） 并且“花色”地位高于“面值”,将逻辑关键字看成由d个关键字复合而成，每个关键字可能取r个值。则从最低位起，按关键字值将记录分配到r个队列之后再收集到一起，如此重复d趟，最终完成整个记录序列的排列。基数指的是r的取值范围。,思路：,10.6 基数排序,基数排序是借助多关键字排序的思想对单逻辑关键字进行排序的方法。,初始关键字,例,第一趟分配,0 1 2 3 4 5 6 7 8 9 10 11,0 1 2 3 4 5 6 7 8 9,第一趟收集,0 1 2 3 4 5 6 7 8 9 10 11,第二趟分配,0 1 2 3 4 5 6 7 8 9,第二趟收集,0 1 2 3 4 5 6 7 8 9 10 11,针对个位数,针对十位数,特点：, 适用于记录数多，但关键字较小的序列。 基数排序为稳定算法。,10.6 基数排序,10.7 各种内部排序算法比较,备注中标有 的方法其时间复杂度与原始序列有关。, 待排记录数n。 一条记录所带信息量的大小。 对排序稳定性的要求。 关键字的分布情况。 算法的时间复杂度和空间复杂度。,选择排序方法时需要考虑以下几个因素