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

《内部排序4选择排序5归并排序6基数排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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选择排序有序序列r1r2ri-1rirnrk…………无序序列rnri+1r1r2ri-1……riri……交换最小记录简单选择排序树形选择排序堆排序思路：一.简单选择排序10.4选择排序每次经n-i次比较，从n-i+1个记录中选出第i小的记录，并与第i位置记录交换。初始关键字493865977

2、6132749i=11338659776492749例i=21327659776493849i=31327389776496549i=41327384976976549i=51327384949976576i=61327384949659776i=71327384949657697每次经n-i次比较，从n-i+1个记录中选出第i小的记录，并与第i位置记录交换。思路：10.4选择排序解决方法：设置一个整型变量index，用于记录在一趟比较的过程中关键码最小的记录位置。212825164908indexindexindex08关键问题⑴:如何在无序

3、区中选出关键码最小的记录？10.4选择排序关键问题⑴:如何在无序区中选出关键码最小的记录？212825164908indexindex08算法描述：index=i;for(j=i+1;j<=L.length;j++)if(L.r[j].key

4、小记录的最终位置？voidSelectSort(SqList&L){for(i=1;i

5、找出键值较小的记录，则可减少后面的选择中所用的比较次数，从而提高整个排序过程的效率。减少关键码间的比较次数查找最小值的同时，找出较小值10.4选择排序ZHAOCHALIUBAODIAOYANGXUEWANGCHABAODIAOWANGBAODIAOBAO锦标赛过程示意图冠军1234567ZHAOCHALIUBAODIAOYANGXUEWANGCHALIUDIAOWANGCHADIAOCHA锦标赛过程示意图亚军89ZHAOCHALIUBAODIAOYANGXUEWANGZHAOLIUDIAOWANGLIUDIAODIAO锦标赛过程示意图季军101

6、1思路：二.树型选择排序10.4选择排序以初始序列作为完全二叉树的叶子结点，从最后的分支结点开始，选左右孩子中较小的(胜者)为其双亲的值，相等则取左孩子，直至选出树根，得到最小元素；然后将此时根对应的叶子结点关键字值改为最大值，从该叶子起与兄弟比，较小的作为新的双亲，直至根，得到次小值…，依次可选出其余元素。134938383865659776131313272749例：4938659776132749二.树型选择排序10.4选择排序以初始序列作为完全二叉树的叶子结点，从最后的分支结点开始，选左右孩子中较小的(胜者)为其双亲的值，相等则取左

7、孩子，直至选出树根，得到最小元素；…274938383865659776∞2776272749二.树型选择排序10.4选择排序例：4938659776132749134938383865659776131313272749然后将此时根对应的叶子结点关键字值改为最大值，从该叶子起与兄弟比，较小的作为新的双亲，直至根，得到次小值…，依次可选出其余元素。缺点：需增加额外空间来存放中间比较结果和排序结果，且算法实现困难。三.堆排序堆的概念：堆是满足下列性质的数列{k1,k2,…,kn}:ki≤k2iki≤k2i+1ki≥k2iki≥k2i+1或若上

8、述数列是堆，则k1必是数列中的最小值或最大值，则称分别满足上式的序列为小顶堆或大顶堆。完全二叉树中所有非终端结点的值均不大于（或不小于）其左右孩子的结