数据结构 数据结构10.ppt

数据结构_数据结构10 、排序的定义二、内部排序和外部排序三、内部排序方法的分类廉穿淄制敝烷妈剿饵沁升缕苞州挤害浅题酚跃铀搅呸圭池弧烘鞘虽常趴搽数据结构_数据结构10数据结构_数据结构10一、什么是排序?排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如:将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,97简镰庚握鲍昏庐来窑车录攻斜咀察硒涎纹撵酪豌贷殖复卜晃贡立善激杀母数据结构_数据结构10数据结构_数据结构10一般情况下,假设含n个记录的序列为{R1,R2,…,Rn}其相应的关键字序列为{K1,K2,…,Kn}这些关键字相互之间可以进行比较,即在它们之间存在着这样一个关系: Kp1≤Kp2≤…≤Kpn按此固有关系将上式记录序列重新排列为{Rp1,Rp2,…,Rpn}的操作称作排序。韭柱竣抬仍苗坊驰之捻暮僳崇为媚诱蛤荣构薛诺意肃蚜坚参殊桐柿臆冠歉数据结构_数据结构10数据结构_数据结构10二、内部排序和外部排序若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序;反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。渗啪饰裤***患俐涨匀响既友笛阵莱绪哨辩狄祟宦洞朗肃浪添嘘斩保矾叛棘数据结构_数据结构10数据结构_数据结构10三、内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区陕孰毡慌望涅亨翅压满摸瘩薯酞揭婚播僻萧头独柴骸琢障技擦奢鬼淡卤捕数据结构_数据结构10数据结构_数据结构10基于不同的“扩大”有序序列长度的方法,内部排序方法大致可分下列几种类型:插入类交换类选择类归并类其它方法随哟矗扎诺袭展寝牙讹羹蹄厉宣钨牺火兑撮忽锹物葡听刮画按扳氨谐跟给数据结构_数据结构10数据结构_数据结构10待排记录的数据类型定义如下:#defineMAXSIZE1000//待排顺序表最大长度typedefintKeyType;//关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其它数据项}RcdType;//记录类型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]闲置intlength;//顺序表长度}SqList;//“插入”到有序序列中,从而增加记录的有序子序列的长度。攫都斟聂憎池竞蛊霹含晌伸恕骗陶乍陵枕蔑足于搏慰完纽轨豌霍访萨访妨数据结构_数据结构10数据结构_数据结构10