电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

数据结构_选择排序_CVIP免费

数据结构_选择排序_C_第1页
1/33
数据结构_选择排序_C_第2页
2/33
数据结构_选择排序_C_第3页
3/33
第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个元素中选出次小的记录交换到第二个位置上,依次类推。初态83916839168391683916kijijik13986互换ij13986ij13986ij第一趟第二趟13986ij第三趟示例:ijkkjk2)简单选择排序算法描述voidSelectSort(ElemR[],intn){//对记录序列R[1..n]作简单选择排序for(i=1;iB,B->C=>A->C例锦标赛在8个运动员中决出前3名至多需要11场比赛CHACHALIU*CHACHAZHAODIAOWANGWANGXUEDIAOYANGDIAO亚军例锦标赛在8个运动员中决出前3名至多需要11场比赛DIAOLIULIU*ZHAO*DIAOWANGWANGXUEDIAOYANGDIAO季军2.树型选择排序1)基本思想又称锦标赛排序,其过程:首先对n个记录的关键字两两比较,然后在n/2个较小者之间再进行两两比较,如此重复,直至选出最小关键字的记录为止。此对应的过程可以用一棵有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}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)则称之为堆。小根堆大根堆例如:判定序列{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交换,如此重复下去,每次重新建堆的元素个数不断减1,直到重新建堆的元素个数仅剩一个为止。这时堆排序已经完成,则排序码k1,k2,k3,…,kn已排成一个有序序列。实...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

数据结构_选择排序_C

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部