排序定义将一个数据元素(或记录)的任意序列 - 副本.ppt

《排序定义将一个数据元素(或记录)的任意序列 - 副本.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Sorting排序排序定义——将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫~排序分类按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序基数排序概述排序：将一组杂乱无章的数据按一定的规律顺次排列起来。数据表(datalist):它是待排序数据对象的有限集合。关键码(key):通常数据对象有多个属性域，即多个

2、数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键码。每个数据表用哪个属性域作为关键码，要视具体的应用需要而定。即使是同一个表，在解决不同问题的场合也可能取不同的域做关键码。主关键码:如果在数据表中各个对象的关键码互不相同，这种关键码即主关键码。按照主关键码进行排序，排序的结果是唯一的。次关键码:数据表中有些对象的关键码可能相同，这种关键码称为次关键码。按照次关键码进行排序，排序的结果可能不唯一。排序算法的稳定性:如果在对象序列中有两个对象r[i]和r[j]，它们的关键码k[i]==k[j

3、]，且在排序之前，对象r[i]排在r[j]前面。如果在排序之后，对象r[i]仍在对象r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。内排序与外排序:内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。各节给出算法运行时间代价的大略估算一般都按平均情况进行估算

4、。对于那些受对象关键码序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算。静态排序:排序的过程是对数据对象本身进行物理地重排，经过比较和判断，将对象移到合适的位置。这时，数据对象一般都存放在一个顺序的表中。动态排序:给每个对象增加一个链接指针，在排序的过程中不移动对象或传送数据，仅通过修改链接指针来改变对象之间的逻辑顺序，从而达到排序的目的。算法执行时所需的附加存储:评价算法好坏的另一标准。静态排序过程中所用到的数据表类定义，体现了抽象数据类型的思想。按排序所需工作量简单的排序方法：T(n)=O

5、(n²)先进的排序方法：T(n)=O(nlogn)基数排序：T(n)=O(d.n)排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置排序方法插入排序选择排序交换排序归并排序直接插入排序折半插入排序简单选择排序堆排序起泡排序快速排序基数排序多关键字排序定义：例对52张扑克牌按以下次序排序：2<3<……<A<2<3<……<A<2<3<……<A<2<3<……<A两个关键字：花色（<<<）面值（2<3<……

6、)：先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列最低位优先法(LSD)：从最低位关键字kd起进行排序，然后再对高一位的关键字排序，……依次重复，直至对最高位关键字k1排序后，便成为一个有序序列MSD与LSD不同特点按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序按LSD排序，不必分成子序列

7、，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序链式基数排序基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法链式基数排序：用链表作存储结构的基数排序链式基数排序步骤设置10个队列，f[i]和e[i]分别为第i个队列的头指针和尾指针第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链

8、表重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列例初始状态：278109063930589184505269008083109589269278063930083184505008e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配