计算机软件基础之数据结构-排序.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、排序的时间复杂性排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少,则认为该方法的时间复杂性就越好,分析一种排序方法,不仅要分析它的时间复杂性,而且要分析它的空间复杂性、稳定性和简单性等。化喇宰誊凰采哥苹韶蛋翟色翠挨汗唱莉斥嫁昧靛陕早雹逆埂滦板偶辈七竣计算机软件基础之数据结构-排序计算机软件基础之