[理学]8-排序.ppt

一、排序的定义(Sorting)？ 简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来（递增或递减）。 排序是计算机中经常遇到的操作。 排序的对象可以是数字型的，也可以是字符型的，按其对应的ASCII码的顺序排列 二、排序的几个基本概念 数据表(Data List) 待排序的数据对象的有限集合。 关键字(Key) 作为排序依据的数据对象中的属性域。 主关键字 不同的数据对象若关键字互不相同，则这种关键字称为主关键字。 排序的确切定义 使一组任意排列的对象变成一组按关键字线性有序的对象。 排序算法的稳定性 判断标准：关键字相同的数据对象在排序过程中是否保持前后次序不变。如 2, 2*,1，排序后若为1, 2*, 2 则该排序方法是不稳定的。 内排序与外排序 区分标准：排序过程是否全部在内存进行。 内部排序一般分为五类：插入排序、选择排序、交换排序、归并排序、分配排序 排序的时间开销 它是衡量算法好坏的最重要的标志。通常用算法执行中的关键字比较次数和数据移动次数来衡量。 一、直接插入排序(Insert Sort) 直接插入排序举例 i (1) (2) (3) (4) (5) (6) temp [21] 25 49 25* 16 08 25 1 [21 25] 49 25* 16 08 49 2 [21 25 49] 25* 16 08 25* 3 [21 25 25* 49] 16 08 16 4 [16 21 25 25* 49] 08 08 5 [08 16 21 25 25* 49] 直接插入排序算法由两重循环组成，对于有n个记录的排序，内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。 若初始时关键字递增有序，这是最好情况。每一趟排序中仅需进行一次关键字的比较，所以总的比较次数为n-1。在while循环之前和之中，至少要移动记录两次，所以总的移动次数为2(n-1)。 若初始时关键字递减有序，这是最坏情况。这时的记录比较和移动次数分别为： 直接插入排序的稳定性 直接插入排序是一种稳定的排序方法。 原理：关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。 希尔排序 1959年由D.L. Shell提出，又称缩小增量排序(Diminishing-increment sort) 。 基本思想：在插入排序中，只比较相邻的结点，一次比较最多把结点移动一个位置。如果对位置间隔较大距离的结点进行比较，使得结点在比较以后能够一次跨过较大的距离，这样就可以提高排序的速度。 希尔排序的基本过程 希尔排序示例 i (0) (1) (2) (3) (4) (5) gap 21 25 49 25* 16 08 1 21 - - 25* 3 25 - - 16 49 - - 08 21 16 08 25* 25 49 2 21 - 08 - 25 2 16 - 25* - 49 08 16 21 25* 25 49 3 08 16 21 25* 25 49 1 08 16 21 25* 25 49 希尔排序中gap的取法 Shell最初的方案是 gap= n/2, gap=gap/2，直到gap=1. Knuth的方案是gap = gap/3+1 其它方案有：都取奇数为好；或gap互质为好等等。 希尔排序的时间复杂度 对希尔排序的复杂度的分析很困难，在特定情况下可以准确地估算关键字的比较和对象移动次数，但是考虑到与增量之间的依赖关系，并要给出完整的数学分析，目前还做不到