1、数据结构第1页，共36页。10.1 概述概述第十章第十章 内部排序内部排序 10.2 插入排序插入排序 10.3 快速排序快速排序 10.4 选择排序选择排序 10.5 归并排序归并排序 10.6 基数排序基数排序 10.7 各种内部排序方法的比较各种内部排序方法的比较第2页，共36页。基本思想：基本思想：每一趟在每一趟在n-i+1(i=1,2,n)个记录中选取关键字最个记录中选取关键字最小的记录作为有序序列中的第小的记录作为有序序列中的第i个记录。个记录。10.4 选择排序选择排序有序序列有序序列12i-1ink无序序列无序序列ni+112i-1ii交换交换最小记录最小记录u简单选择排序简单
2、选择排序u树形选择排序树形选择排序u堆排序堆排序第3页，共36页。思路：思路：一一.简单选择排序简单选择排序 10.4 选择排序选择排序 每次经每次经 n-i 次比较，从次比较，从 n-i+1个记录中选出第个记录中选出第 i 小的记录，并与第小的记录，并与第 i 位置记录交换。位置记录交换。第4页，共36页。初始关键字初始关键字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
3、 65 49i=5i=513 27 38 49 49 97 65 76i=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 位置记录交换。位置记录交换。思路：思路：第5页，共36页。10.4 选择排序选择排序解决方法：解决方法：设置一个整型变量设置一个整型变量index，用于记录在一趟比较的，用于记录在一趟比较的过程中关键码最小的记录位置。过程中关键码最小的记录位置。indexindexindex关键问题关
4、键问题:如何在无序区中选出关键码最小的记录？如何在无序区中选出关键码最小的记录？第6页，共36页。10.4 选择排序选择排序关键问题关键问题:如何在无序区中选出关键码最小的记录？如何在无序区中选出关键码最小的记录？indexindex算法描述：算法描述：index=i;for(j=i+1;j=L.length;j+)if(L.(L.rj.keyL.rindex.key)index=j;第7页，共36页。解决方法：解决方法：第第i趟简单选择排序的待排序区间是趟简单选择排序的待排序区间是ri rn，则，则ri是无是无序区第一个记录，所以，将序区第一个记录，所以，将index所记载的关键码最小的记录
5、所记载的关键码最小的记录与与ri交换。交换。算法描述：算法描述：if(index!=i)L.riL.rindex;10.4 选择排序选择排序关键问题关键问题：如何确定最小记录的最终位置？如何确定最小记录的最终位置？第8页，共36页。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 记录交换记
6、录交换 算法：算法：特点：特点：1)1)时间复杂度为时间复杂度为O(nO(n2 2)2)2)算法稳定算法稳定第9页，共36页。改进的着眼点：改进的着眼点：如何如何减少减少关键码间的关键码间的比较比较次数。次数。若能利用每趟比较后的结果，也就是在找出键值最小记录的若能利用每趟比较后的结果，也就是在找出键值最小记录的同时，也找出键值较小的记录，则可减少后面的选择中所用同时，也找出键值较小的记录，则可减少后面的选择中所用的比较次数，从而提高整个排序过程的效率。的比较次数，从而提高整个排序过程的效率。减少关键码间的比较次数减少关键码间的比较次数查找最小值的同时，找出较小值查找最小值的同时，找出较小值
7、10.4 选择排序选择排序第10页，共36页。ZHAOCHALIUBAODIAOYANGXUEWANGCHABAODIAOWANGBAODIAOBAO锦标赛过程示意图锦标赛过程示意图冠军冠军1234567第11页，共36页。ZHAOCHALIUBAODIAOYANGXUEWANGCHALIUDIAOWANGCHADIAOCHA锦标赛过程示意图锦标赛过程示意图亚军亚军89第12页，共36页。ZHAOCHALIUBAODIAOYANGXUEWANGZHAOLIUDIAOWANGLIUDIAODIAO锦标赛过程示意图锦标赛过程示意图季军季军1011第13页，共36页。思路：思路：二二.树型选择排序树
8、型选择排序 10.4 选择排序选择排序 以初始序列作为完全二叉树的叶子结点，从最后以初始序列作为完全二叉树的叶子结点，从最后的分支结点开始，选左右孩子中较小的的分支结点开始，选左右孩子中较小的(胜者胜者)为其双为其双亲的值，亲的值，相等则取左孩子，直至选出树根，得到最小相等则取左孩子，直至选出树根，得到最小元素；元素；然后将此时根对应的叶子结点关键字值改为然后将此时根对应的叶子结点关键字值改为 最大值最大值，从该叶子起与兄弟比，较小的作为新的双亲，从该叶子起与兄弟比，较小的作为新的双亲，直至根，得到次小值直至根，得到次小值，依次可选出其余元素。，依次可选出其余元素。第14页，共36页。1313
9、 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二二.树型选择排序树型选择排序 10.4 选择排序选择排序 以初始序列作为完全二叉树的叶子结点，以初始序列作为完全二叉树的叶子结点，从最后的分支结点开始，选左右孩子中较小从最后的分支结点开始，选左右孩子中较小的的(胜者胜者)为其双亲的值，为其双亲的值，相等则取左孩子，相等则取左孩子，直至选出树根，得到最小元素；直至选出树根，得到最小元素；第15页，共36页。27
10、27 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 27 49491313 49 49 38 38 3838 3838 6565 65 65 97 977676131313131313 2727 27 27 4949然后将此时根对应的叶子结点关键字值然后将此时根对应的叶子结点关键字值改为改为 最大值最大值，从该叶子起与兄弟比，较，从该叶子起与兄弟比，较小的作为新的双亲，直
11、至根，得到次小小的作为新的双亲，直至根，得到次小值值，依次可选出其余元素。，依次可选出其余元素。缺点缺点：需增加额外空间来：需增加额外空间来存放中间比较结果和排序存放中间比较结果和排序结果，且算法实现困难。结果，且算法实现困难。第16页，共36页。三三.堆排序堆排序 堆的概念：堆的概念：堆堆是满足下列性质的数列是满足下列性质的数列k1,k2,kn:kik2ikik2i+1kik2ikik2i+1或或 若上述数列是若上述数列是堆堆，则，则k1必是数列中的最小值或最大值，必是数列中的最小值或最大值，则称分别满足上式的序列为则称分别满足上式的序列为小顶堆小顶堆或或大顶堆大顶堆。完全二叉树中所有非终端
12、结点的值均不大于（或不小于）完全二叉树中所有非终端结点的值均不大于（或不小于）其左右孩子的结点的值。其左右孩子的结点的值。10.4 选择排序选择排序第17页，共36页。如如堆堆9696，8383，2727，3838，1111，0909堆堆1212，3636，2424，8585，4747，3030，5353，9191968327381109大顶堆大顶堆1236244785533091小顶堆小顶堆三三.堆排序堆排序 10.4 选择排序选择排序第18页，共36页。堆和序列的关系堆和序列的关系将堆用顺序存储结构来存储，则堆对应一组序列。将堆用顺序存储结构来存储，则堆对应一组序列。50384540283
13、63220182850 38 45 32 36 40 28 20 18 281 2 3 4 5 6 7 8 9 10采用顺序存储采用顺序存储 10.4 选择排序选择排序第19页，共36页。三三.堆排序堆排序 堆排序的概念：堆排序的概念：在输出堆顶元素后，使得剩余的在输出堆顶元素后，使得剩余的n-1个元素重又个元素重又形成堆，以便再次输出新的堆顶元素。如此反复执行，形成堆，以便再次输出新的堆顶元素。如此反复执行，最终形成一个有序序列的过程称为堆排序。最终形成一个有序序列的过程称为堆排序。10.4 选择排序选择排序ni+112i-1ii无序区无序区为一个堆为一个堆有序区有序区已经位于最终位置已经位
14、于最终位置第20页，共36页。关键问题关键问题：如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？282516321836163216282518362532162818362528323628161825解决方法：解决方法：由一个无序序列由一个无序序列建堆的过程就是反复建堆的过程就是反复“筛选筛选”的过程。假设最后一个结点的过程。假设最后一个结点（叶子）的序号是（叶子）的序号是n，则最，则最后一个分支结点即为结点后一个分支结点即为结点n的双亲，其序号是的双亲，其序号是n/2。“筛筛选选”即从即从第第n/2个元素个元素开始。开始。第21页，共36页。32362816182536 28
15、 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交交换。换。第22页，共36页。关键问题关键问题:如何调整剩余记录成为一个新堆？如何调整剩余记录成为一个新堆？32162836182516解决方法：解决方法：此时根结点的左右子树均为堆，只需调整根此时根结点的左右子树均为堆，只需调整根结点，与其左右子树根结点中的较
16、大或较小值交换，结点，与其左右子树根结点中的较大或较小值交换，若交换后破坏了子树的若交换后破坏了子树的“堆堆”，则继续调整。，则继续调整。281632361825281618363225第23页，共36页。创建初始堆创建初始堆4938977649651327493897764965132749389776491365271338977649276549被筛选后建成的新堆被筛选后建成的新堆例：无序序列例：无序序列49,38,65,97,76,13,27,49利用堆排序的利用堆排序的 方法进行降序排序方法进行降序排序建小顶堆。建小顶堆。第24页，共36页。输出堆顶元素，调整建新堆输出堆顶元素，调整
17、建新堆133897764927654997381376492765492738137649496597973813764949652738491376974965276549769749381327第25页，共36页。6549769749654976974965499776659749769765769776657697形成降序序列：形成降序序列：97，76，65，49，49，38，27，133813273813274938132749381327494938132749 4938132765 49 49 381327第26页，共36页。特点：特点：堆排序适用于记录数较多的文件进行排序的情况。
18、堆排序适用于记录数较多的文件进行排序的情况。堆排序为不稳定算法。堆排序为不稳定算法。三三.堆排序堆排序 10.4 选择排序选择排序第27页，共36页。将两个或两个以上的有序表组合成一个新的有序将两个或两个以上的有序表组合成一个新的有序表。即假设初始序列有表。即假设初始序列有n个记录，可看成是个记录，可看成是n个长度为个长度为1的有序子序列，将其两两归并，得到的有序子序列，将其两两归并，得到n/2个长度为个长度为2或或1的有序子序列；再将其两两归并。如此重复，直至得的有序子序列；再将其两两归并。如此重复，直至得到一个长度为到一个长度为n的有序序列为止。的有序序列为止。思路：思路：10.5 归并排
19、序归并排序第28页，共36页。例例初始关键字初始关键字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 特点：特点：归并排序为稳定算法，但在一般情况下很少利归并排序为稳定算法，但在一般情况下很少利用用22路归并排序来操作，因其算法实用性较差。路归并排序来操作，因其算法实用性较差。22路归并排序算法路归并排序算法第29页，共36页。10.6 基数排序基数排序 基数排序是借助基数排序是借助多关键字排序多关键字排序的思想
20、对单逻辑关键的思想对单逻辑关键字进行排序的方法。字进行排序的方法。例例 对对52张扑克牌按以下次序排序：张扑克牌按以下次序排序：2 3 A 2 3 A 2 3 A 2 3 A两个关键字：花色（两个关键字：花色（）面值（面值（23A）并且并且“花色花色”地位高于地位高于“面值面值”第30页，共36页。将逻辑关键字看成由将逻辑关键字看成由d个关键字复合而成，每个个关键字复合而成，每个关键字可能取关键字可能取r个值。则从最低位起，按关键字值将个值。则从最低位起，按关键字值将记录记录分配分配到到r个队列之后再个队列之后再收集收集到一起，如此重复到一起，如此重复d趟，最终完成整个记录序列的排列。趟，最终
21、完成整个记录序列的排列。基数指的是基数指的是r的取值范围的取值范围。思路：思路：10.6 基数排序基数排序 基数排序是借助多关键字排序的思想对单逻辑关基数排序是借助多关键字排序的思想对单逻辑关键字进行排序的方法。键字进行排序的方法。第31页，共36页。初始关键字初始关键字例例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 09 89 690 1
22、 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针对个位数针对个位数针对十位数针对十位数第32页，共36页。特点：特点：适用于记录数多，但关键字较小的序列。适用于记录数多，但关键字较小的序列。基数排序为稳定算法。基数排序为稳定算法。10.6 基数排序基数排序第33页，共36页。10.7 各种内部排序算法比较各种内部排序算法比较方法方法 平均时间平均时
23、间 最坏情况最坏情况 辅助存储辅助存储 稳定稳定 备备 注注直接插入直接插入 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备注中标有备注中标有 的方法其时间复杂度与原始序列有关。的方法其时间复杂度与原始序列有关。第34页，共36页。待排记录数待排记录数n
24、。一条记录所带信息量的大小。一条记录所带信息量的大小。对排序稳定性的要求。对排序稳定性的要求。关键字的分布情况。关键字的分布情况。算法的时间复杂度和空间复杂度。算法的时间复杂度和空间复杂度。选择排序方法时需要考虑以下几个因素：选择排序方法时需要考虑以下几个因素：10.7 各种内部排序算法比较各种内部排序算法比较第35页，共36页。1.已知数据序列为已知数据序列为(12，5，9，20，6，31，24)，对该数据序列进行排序，写出简单选择排序、堆对该数据序列进行排序，写出简单选择排序、堆排序、二路归并排序每趟的结果。排序、二路归并排序每趟的结果。2.设要将序列（设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的）中的关键码按字母序的升序重新排列，则：关键码按字母序的升序重新排列，则：二路归并排序一趟扫描的结果是二路归并排序一趟扫描的结果是 ；堆排序初始；堆排序初始建小顶堆的结果是建小顶堆的结果是 。第36页，共36页。
