数据结构-内部排序试卷.ppt

1．稳定性 归并排序是稳定的排序方法。 2．时间复杂度 为O(nlog2n)。 3．空间复杂度 为O(n)。 ? 10.5 归 并 排 序 五、算法分析 10.6 基数排序 一、多关键字的排序 二、链式基数排序 10.6 基数排序 1.基数排序不用进行记录关键字的比较和交换， 而是利用关键字的结构，通过“分类”和“收集”的办法 实现排序。 2.基数排序将多关键字排序的思想用于单逻辑关键字的排序中。 10.6 基 数 排 序 一、多关键字的排序 1．多关键字排序思想 以扑克牌排序为例，讨论多关键字排序思想。 任何一张扑克牌都有花色和面值两种属性，以花色为第一关键字K1，面值为第二关键字K2，都可看成由K1和K2组成的复合关键字。任一张牌的关键字为K1K2。 多关键字排序，就是按复合关键字的大小排序。 具体到扑克牌排序，有两种方法： 第一种是先花色后面值：按花色分为四类有序，然后每类按面值从小到大排序； 第二种是先面值后花色：先将牌按面值分为13类，然后从小到大将它们收集起来，再按花色分为4堆，最后按花色顺序收集起来。 2．多关键字排序定义 设有n个记录的序列{R1,R2,…,Rn}，且每个记录Ri中含有d个关键字(Ki0,Ki1,…Kid-1)，规定Ki0 为主位关键字(或最高位关键字)，Kid-1为次位关键字(最低位关键字)。 序列{R1,R2,…,Rn}对关键字(Ki0,Ki1,…Kid-1)有序是指：对于序列中任意两个记录Ri的Rj(1≤i≤j≤n)都满足下列有序关系：(Ki0,Ki1,…Kid-1) (Kj0,Kj1,…Kjd-1)。 10.6 基 数 排 序 一、多关键字的排序 3. 两种排序方法 (1)最高位优先(MSD) 先对最主位关键字K0进行排序，具有相同的K0值的记录构成一个子序列，再对关键字K1进行排序，依次重复，直到对Kd-1排序，最后将所有子序列依次连接在一起成为一个有序序列。 将序列逐层分割若干子序列。 (2)最低位优先(LSD) 从最次位关键字Kd-1起进行排序，然后再对Kd-2 进行排序，依次重复，直到对K0 进行排序后便成为一个有序序列。 不必分成子序列，对每个关键字都是整个序列参加排序。 10.6 基 数 排 序 一、多关键字的排序 例：记录序列为(ABC,ACD,BBC,BAD,ACB，CAD)。 MSD：ABC ABC ABC LSD:ACB BAD ABC ACD ACD ACB ABC CAD ACB ACB ACB ACD BBC ABC ACD BBC BAD BAD ACD BBC BAD BAD BBC BBC BAD ACB BBC CAD CAD CAD CAD ACD CAD 10.6 基 数 排 序 一、多关键字的排序 二、链式基数排序 1．基数排序思想 采用LSD方法进行的排序。即借助“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法。 逻辑关键字可以看成由d个关键字复合而成的，而且其中的关键字都具有相同的取值范围(如数字0≤Ki≤9，字母’A’≤Ki≤’Z’)，具有这样特征的关键字，可按LSD进行排序，只要从最低数位关键字起，按关键字的不同值将序列中记录“分配”到R个队列中后再“收集”，如此反复d次。这就是基数排序，这里“基”指的是R的取值范围，实际上这里的“基数”有类似进制数中基数的含义。 10.6 基 数 排 序 2. 基数排序的方法 (1)首先根据所选择的基数，设定r个队列。 (2)按LSD法，把n个关键字按最低位Kd的值分配到相应队列中。 (3)再把r个队列从小到大，首尾相接收集起来，此时n个关键字已按最低位Kd的值排好序，这称为第一趟分配收集。 (4)接着按次最低位的值，把第一趟收集起来的关键字再分配到相应队列中，然后进行上述类似收集工作，这就完成了第二趟分配收集。 对所有的关键字重复分配收集的过程。最后一趟分配收集的结果，就是一个按关键字从小到大有序的记录序列。因此基数排序需要作d趟分配和收集。 二、链式基数排序 10.6 基 数 排 序 3. 基数排序的算法 (1)记录的存储结构 在基数排序中，为