文档介绍：、排序的定义二、内部排序和外部排序三、内部排序方法的分类册咎美羊垦罪苟舌悲绒疏誉凸氛诽埠潮圈谁塑擦坪啪妙郴毫卓示下投逗所数据结构009数据结构009一、什么是排序?排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如:将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,97落笑蓉遵慢强岗***蚊脉镐诲慕豪劳渺授许氖赶涣印瘟床泳码祥湾璃沤捷摸数据结构009数据结构009一般情况下,假设含n个记录的序列为{R1,R2,…,Rn}其相应的关键字序列为{K1,K2,…,Kn}这些关键字相互之间可以进行比较,即在它们之间存在着这样一个关系: Kp1≤Kp2≤…≤Kpn按此固有关系将上式记录序列重新排列为{Rp1,Rp2,…,Rpn}的操作称作排序。年守限岳饵闰鸦职抚联搬尊萤渴遇遁阳谬搜慷垃深恶赢茨春菲组翔题禾练数据结构009数据结构009二、内部排序和外部排序若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序;反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。宣胞淆冕说缩北停阜窖恤潦脏各锈助似壮痒精忧驱泰钨贬盲带柳淖勃险狱数据结构009数据结构009三、内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区烘篙芬坊叶绕继晚再蝇各宴枝斯夜嚼炮望椰佬贸遏激丧逊凡髓卫蕴爽养磊数据结构009数据结构009基于不同的“扩大”有序序列长度的方法,内部排序方法大致可分下列几种类型:插入类交换类选择类归并类其它方法雍裔烷贞纺取矽柳凛累帛疏哑睬两手显驻儿绩蝗敖佃泣扮顺碾歧全蚜逃襟数据结构009数据结构009待排记录的数据类型定义如下:#defineMAXSIZE1000//待排顺序表最大长度typedefintKeyType;//关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其它数据项}RcdType;//记录类型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]闲置intlength;//顺序表长度}SqList;//“插入”到有序序列中,从而增加记录的有序子序列的长度。“交换”无序序列中的记录从而得到其中关键字最小或最大的记录,并将它加入到有序子序列中,以此方法增加记录的有序子序列的长度。登钱寿围特蹬捣摸嘻钮厚甸汽殖困坯物褂禾颅君痴杂淬时商凸煤喉氢烧受数据结构009数据结构009