数据结构_选择排序_C

《数据结构_选择排序_C》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第10章内部排序10.1排序的基本概念10.2插入排序10.3交换排序10.4选择排序10.5归并排序10.6基数排序10.7各种内部排序方法的比较10.4选择排序基本思想：第i趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中的第i个记录。1.简单选择排序2.树形选择排序3.堆排序1）简单选择排序的基本思想通过n-i次关键字间的比较，从无序序列[i..n]的n-i+1记录中选出关键字最小的记录加入有序序列（即作为有序序列中的第i个记录）。1.简单选择排序首先从1--n个元素中选出关键字最小的记录交换到第一个位置上。然后再从第2个到第n个

2、元素中选出次小的记录交换到第二个位置上，依次类推。初态83916839168391683916kijijik13986互换ij13986ij13986ij第一趟第二趟13986ij第三趟示例：ijkkjk2）简单选择排序算法描述voidSelectSort(ElemR[],intn){//对记录序列R[1..n]作简单选择排序for(i=1;i

3、稳定的”。算法实现共需要进行n-1次选择，每次选择需要进行n-i次比较（1≤i≤n-1），而每次交换最多需3次移动，因此，总的比较次数C=n(n-1)/2，总的移动次数M=3(n-1)。故其时间复杂度为O(n2)。选择排序的主要操作是进行关键字间的比较，因此改进选择排序应从如何减少“比较”考虑。显然，在n个关键字中选出最小值，至少进行n-1次比较，然而，继续在剩余的n-1个关键字中选择次小值，是否一定要进行n-2次比较呢？如果能利用前n-1次比较所得信息，就可减少以后各趟选择排序中所用的比较次数。实际上，体育比赛中的锦标赛便是一种选择排序例锦标赛在8个运动员中决出前3名

4、至多需要11场比赛BAOBAOBAOBAOLIUCHACHAZHAODIAOWANGWANGXUEDIAOYANGDIAO冠军前提：A->B，B->C=>A->C例锦标赛在8个运动员中决出前3名至多需要11场比赛CHACHALIU*CHACHAZHAODIAOWANGWANGXUEDIAOYANGDIAO亚军例锦标赛在8个运动员中决出前3名至多需要11场比赛DIAOLIULIU*ZHAO*DIAOWANGWANGXUEDIAOYANGDIAO季军2.树型选择排序1）基本思想又称锦标赛排序，其过程：首先对n个记录的关键字两两比较，然后在n/2个较小者之间再进行两两比较

5、，如此重复，直至选出最小关键字的记录为止。此对应的过程可以用一棵有n个叶子结点的完全二叉树表示。ABCDEFGHACEGAEAABCDEFACEGAEA493865977613274938651327381313例从{49，38，65，97，76，13，27，49}8个关键字中选出最小关键字的过程。输出134938659776∞274938657627382727例从{49，38，65，97，76，13，27，50}8个关键字中选出最小关键字的过程输出13，274938659776∞∞4938657649384938例从{49，38，65，97，76，13，27，50}

6、8个关键字中选出最小关键字的过程输出13，27，38除了最小关键字之外，每次选择比较的次数为：完全二叉树的深度-1次2）树型选择排序算法分析含n个叶子结点的完全二叉树的深度为㏒2n+1，因此在树型选择排序中，除了最小关键字之外，每选择一个次小关键字仅需进行㏒2n次比较，因此，其时间复杂度为O(n㏒2n)。由于此种排序方法需要的存储空间较多和最大值多余的比较多等缺点，堆排序应运而生。3.堆排序1）堆的定义n个元素的序列{k1,k2,k3…,kn}当且仅当满足关系：ki≤k2i，ki≤k2i+1或ki≥k2i，ki≥k2i+1（i=1，2，3，．．．，n/2）则

7、称之为堆。小根堆大根堆例如：判定序列｛96，83，27，38，11，09｝、｛12，36，24，85，47，30，53，91｝是否堆968327380911将排序码按顺序组成一棵完全二叉树，则易判别。小根堆：二叉树的所有根结点值小于或等于左右孩子的值；大根堆：二叉树的所有根结点值大于或等于左右孩子的值；12362485304753912）堆排序的基本思想将堆中第一个结点（二叉树根结点）和最后一个结点的数据进行交换（k1与kn），再将k1～kn-1重新建堆，然后k1和kn-1交换，再将k1～kn-2重新建堆，然后k1和kn-2交换，如此重复