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

2017 年2月 25 日星期六 1数据结构之排序数据结构之排序 2017 年2月 25 日星期六 2 基本概念排序介绍 排序( Sorting ) 是数据处理中一种很重要的运算,同时也是很常用的运算,一般数据处理工作 25% 的时间都在进行排序。简单地说,排序就是把一组记录(元素) 按照某个域的值的递增(即由小到大)或递减(即由大到小)次序重新排列的过程。 2017 年2月 25 日星期六 3 表1 学生档案表女 16 李小燕 99006 男 20 周涛 99005 女 18 张丽娟 99004 女 17 谢宁 99003 男 19 林一鹏 99002 男 18 王晓佳 99001 性别年龄姓名学号 2017 年2月 25 日星期六 4 例如,在表 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按年龄的递增排序结果。 2017 年2月 25 日星期六 5 基本概念 1、排序码( Sort Key )即:排序关键字 作为排序依据的记录中的一个属性。它可以是任何一种可比的有序数据类型,它可以是记录的关键字,也可以是任何非关键字。如上例中的学生年龄。在此我们认为对任何一种记录都可找到一个取得它排序码的函数 Skey (一个或多个关键字的组合)。 2、有序表与无序表 一组记录按排序码的递增或递减次序排列得到的结果被称之为有序表,相应地,把排序前的状态称为无序表。 2017 年2月 25 日星期六 6 3、正序表与逆序表 若有序表是按排序码升序排列的,则称为升序表或正序表,否则称为降序表或逆序表。我们一般只讨论正序表。 4、排序定义 若给定一组记录序列 r 1 ,r 2,…,r n, 其排序码分别为 s 1,s 2,…,s n, 将这些记录排成顺序为 r k1 , r k2,…,r kn 的一个序列 R’, 满足条件 s k1≤s k2≤…≤s kn, 获得这些记录排成顺序为 r p1 , r p2,…,r pn 的一个序列 R”, 满足条件 s p1≤s p2≤…≤s pn的过程称为排序。 也可以说,将一组记录按某排序码递增或递减排列的过程,称为排序。 2017 年2月 25 日星期六 7 5、稳定与不稳定 因为排序码可以不是记录的关键字,同一排序码值可能对应多个记录。对于具有同一排序码的多个记录来说,若采用的排序方法使排序后记录的相对次序不变,则称此排序方法是稳定的,否则称为不稳定的。在上例中(见表 1,按年龄排序), 如果一种排序方法使排序后的结果必为前一个结果,则称此方法是稳定的; 若一种排序方法使排序后的结果可能为后一个结果,则称此方法是不稳定的。 2017 年2月 25 日星期六 8 6、内排序与外排序 按照排序过程中使用内外存的不同将排序方法分为内排序和外排序。若排序过程全部在内存中进行,则称为内排序; 若排序过程需要不断地进行内存和外存之间的数据交换,则称为外排序。 2017 年2月 25 日星期六 9 内排序大致可分为五类: 插入排序、选择排序、交换排序、归并排序基数排序。本章仅讨论内排序。 2017 年2月 25 日星期六 10 7、排序的时间复杂性 排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少,则认为该方法的时间复杂性就越好,分析一种排序方法,不仅要分析它的时间复杂性,而且要分析它的空间复杂性、稳定性和简单性等。