文档介绍：第八章排序排序及基本算法为了便于检索,人们通常希望能在计算机中保存的数据是按关键字值大小排列的有序表。这是因为对于有序表可以采用检索效率较高的二分法检索算法,其平均检索长度为log2(n+1)-1;而对于无序表只能进行顺序检索,其平均检索长度为(n+1)/2。又如为了方便检索,需要构造二叉检索树、B树和B+树等树表,构造这些树表的过程本身就是一个排序的过程。在现今的计算机系统中,有相当大的一部分CPU时间开销是用于对数据的排序整理上的。因此,学习和研究各种排序算法,分析并设计出高效适用的排序算法,是计算机科学工作者的重要课题之一。,其功能是将一组数据元素(或记录)的任意序列,经重新排列整理成为按关键字值大小有序的序列。排序的实际应用领域也是非常广泛的。例如在实际问题的数据处理中常会遇到这样的情况,需要把若干名字如人名、地名、国名、书名、校名、物名等按字母顺序列表;需要把若干数值如各种考试分数、田赛的长度、径赛的时间等按成绩次序排名;需要把若干不同属性的记录按照某种方法排列次序……。所有这些都是排序问题,都需要把一组数据元素或记录按照某种特定的次序排列起来。排序的基本概念(续)排序的确切定义可以描述为:设(R1,R2…Rn)是某文件的n个记录,其相应的关键字为(K1,K2…Kn)。排序(sort)是这样一种操作,它确定文件中n个记录的一种排列(Rj1,Rj2…Rjn),使得其相应关键字满足递增(即不减)关系Kj1≤Kj2≤…≤Kjn或递减(即不增)关系Kj1≥Kj2≥…≥Kjn。若关键字满足递增(即不减)关系时,称作按关键字升序排序(ascendingsort);若关键字满足递减(即不增)关系时,称作按关键字降序排序(descendingsort)。排序的基本概念(续)在前面定义中,关键字Ki(i=1,2…n)称作排序码(sortcode)。排序码可以是记录的主关键字,也可以是次关键字,或者是多个关键字的组合(即组合关键字)。当排序码是主关键字时,由于主关键字可以惟一标识一个记录,所以排序结果是惟一的。当排序码是次关键字时,同一关键字值可能标识了两个或两个以上的记录,所以排序结果不惟一。排序的基本概念(续)若相同关键字值的记录在排序前后的相对位置不会发生改变,即若Ri与Rj的关键字相同(Ki=Kj)且在排序前Ri在Rj之前,排序后的Ri仍在Rj之前,则称所用的排序算法是稳定的(stable);否则,若排序前后相同关键字值的记录其相对位置可能发生改变,即排序之后的序列中有可能出现Rj在Ri之前的情况,则称所用的排序算法是不稳定的。当排序码是组合关键字时,通常称作多关键字排序,其排序结果的惟一性取决于组合关键字是否能惟一标识一个记录。排序的分类根据排序过程中待排序文件存放的位置不同,可以把排序分为内部和外部排序两大类。内部排序是指待排序文件放在内存中进行排序的排序;内部排序适用于记录个数不很多的较小待排序文件的排序;外部排序是指在待排序文件很大时,内存中不能一次容纳全部记录,还要借助于外存存放待排序文件,在排序过程中需要对外存进行访问的排序;外部排序则适用于记录个数太多不能一次全部放入内存的较大待排序文件的排序。排序的分类(续)按排序中所用策略的不同:内部排序通常可以分为:插入排序选择排序交换排序归并排序分配排序每一类中不同的排序算法都是基于同一策略的不同方法。外部排序多是采用多路归并方法进行排序。排序的分类(续)按排序中所需的工作量分类:简单的排序方法,其时间复杂度为O(n2)。先进的排序方法,其时间复杂度为O(nlogn)。基数排序,其时间复杂度为O(d·n)。