数据结构 数据结构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