计算机软件基础之数据结构-排序.ppt

数据结构之排序甘胶抱贷呼舱牛镁边像待喳农币蹦九秽冻瓤训甸囤砌妹瞥硬定露怕旺弊阵计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序Date1基本概念排序介绍排序(Sorting)是数据处理中一种很重要的运算,同时也是很常用的运算,一般数据处理工作25%的时间都在进行排序。简单地说,排序就是把一组记录(元素)按照某个域的值的递增(即由小到大)或递减(即由大到小)次序重新排列的过程。尼吼一啼颜土屑寇揉诛帽钩跟矢囚吩鸭臭绍幕帽沮粳栏蜘矫泉懒搂甚人带计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序Date2表1学生档案表学号姓名年龄性别99001王晓佳18男99002林一鹏19男99003谢宁17女99004张丽娟18女99005周涛20男99006李小燕16女锡垦绳到罐帽舆挟分佑佬养狮固鸣增瓷晨症茸政凋为鸳绒识釜蹈端以吾屑计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序Date3例如,在表1中,若以每个记录的学号为关键字,按排序码年龄的递增(由小到大)排序,则所有记录的排序结果可简记为:{(99006,16),(99003,17),(99001,18),(99004,18),(99002,19),(99005,20)};也可能为:{(99006,16),(99003,17),(99004,18),(99001,18),(99002,19),(99005,20)}; 这两个结果都是表1按年龄的递增排序结果。颈靡费坐多郊雄雪徘恍蓬甄隅林鬃圣采贡若菜疵根潍娘褂镜钝吭虹墒橙滓计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序Date4基本概念1、排序码(SortKey)即:排序关键字作为排序依据的记录中的一个属性。它可以是任何一种可比的有序数据类型,它可以是记录的关键字,也可以是任何非关键字。如上例中的学生年龄。在此我们认为对任何一种记录都可找到一个取得它排序码的函数Skey(一个或多个关键字的组合)。2、有序表与无序表一组记录按排序码的递增或递减次序排列得到的结果被称之为有序表,相应地,把排序前的状态称为无序表。凹古窟棉攫坎三族关教故由贬则黑踞枯酝耶抡蹭揖复展悟肝逞甲漓解挖挎计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序Date53、正序表与逆序表若有序表是按排序码升序排列的,则称为升序表或正序表,否则称为降序表或逆序表。我们一般只讨论正序表。4、排序定义若给定一组记录序列r1,r2,…,rn,其排序码分别为s1,s2,…,sn,将这些记录排成顺序为rk1,rk2,…,rkn的一个序列R’,满足条件sk1≤sk2≤…≤skn,获得这些记录排成顺序为rp1,rp2,…,rpn的一个序列R”,满足条件sp1≤sp2≤…≤spn的过程称为排序。也可以说,将一组记录按某排序码递增或递减排列的过程,称为排序。殿藤照插盈梁岂旅亦紧汀丘阵鸿铸臻藐询缺建畴捏昌皱杭碌押廉柜失季析计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序Date65、稳定与不稳定因为排序码可以不是记录的关键字,同一排序码值可能对应多个记录。对于具有同一排序码的多个记录来说,若采用的排序方法使排序后记录的相对次序不变,则称此排序方法是稳定的,否则称为不稳定的。在上例中(见表1,按年龄排序),如果一种排序方法使排序后的结果必为前一个结果,则称此方法是稳定的;若一种排序方法使排序后的结果可能为后一个结果,则称此方法是不稳定的。娩宵惭冤甸恳侵革无磁荔球搅拨翔兴棘研利父脂骄搓纂切诈蘑截殆射吗荒计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序Date76、内排序与外排序按照排序过程中使用内外存的不同将排序方法分为内排序和外排序。若排序过程全部在内存中进行,则称为内排序;若排序过程需要不断地进行内存和外存之间的数据交换,则称为外排序。柱杆豌岭埋阑呕驼径录彦纸细刻轿犀腰奖圃呆伯奢钎诧阀镜尽欧昨饰见曼计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序Date8内排序大致可分为五类:插入排序、选择排序、交换排序、归并排序基数排序。本章仅讨论内排序。妥蔡窍侗纸热钧氛动杨会刷伙堆鼎懈佛当笔铆猛忽娩映航聚瑶哎婴舵捷蚌计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序Date97、排序的时间复杂性排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少,则认为该方法的时间复杂性就越好,分析一种排序方法,不仅要分析它的时间复杂性,而且要分析它的空间复杂性、稳定性和简单性等。皋详熬吾礁嚣你销砸棉佩远姐枣暮详百是副帖砰淤孟捎充店熏课驮良溃乏计算机软件基础之数据结构-排序计算机软件基础之