数据结构 第10章_内排序.ppt

再分别对每组中对象根据关键码K2进行排序，按K2值的不同，再分成若干个更小的子组，每个子组中的对象具有相同的K1和K2值。 依此重复，直到对关键码Kd完成排序为止。 最后，把所有子组中的对象依次连接起来，就得到一个有序的对象序列。 最低位优先法首先依据最低位关键码Kd对所有对象进行一趟排序，再依据次低位关键码Kd-1对上一趟排序的结果再排序，依次重复，直到依据关键码K1最后一趟排序完成，就可以得到一个有序的序列。使用这种排序方法对每一个关键码进行排序时，不需要再分组，而是整个对象组都参加排序。 LSD和MSD方法也可应用于对一个关键码进行的排序。此时可将单关键码 Ki 看作是一个子关键码组： 链式基数排序 基数排序是典型的LSD排序方法，利用“分配”和“收集”两种运算对单关键码进行排序。在这种方法中，把单关键码 Ki 看成是一个d元组： 其中的每一个分量 ( 1? j ? d ) 也可看成是一个关键码。 分量 (1 ? j ? d ) 有radix种取值，则称radix为基数。例如，关键码984可以看成是一个3元组(9, 8, 4)，每一位有0, 1, …, 9等10种取值，基数radix = 10。关键码‘data’可以看成是一个4元组(d, a, t, a)，每一位有‘a’, ‘b’, …, ‘z’等26种取值，radix = 26。 针对d元组中的每一位分量，把对象序列中的所有对象, 按 的取值，先“分配”到rd个队列中去。然后再按各队列的顺序，依次把对象从队列中“收集”起来，这样所有对象按取值 排序完成。 如果对于所有对象的关键码K0, K1, …, Kn-1，依次对各位的分量，让 j = d, d-1, …, 1，分别用这种“分配”、“收集”的运算逐趟进行排序，在最后一趟“分配”、“收集” 完成后，所有对象就按其关键码的值从小到大排好序了。 各队列采用链式队列结构，分配到同一队列的关键码用链接指针链接起来。每一队列设置两 个队列指针： int front [radix]指示队头， int rear [radix] 指向队尾。 为了有效地存储和重排 n 个待排序对象，以静态链表作为它们的存储结构。在对象重排时不必移动对象，只需修改各对象的链接指针即可。 基数排序的“分配”与“收集”过程 第一趟 614 921 485 637 738 101 215 530 790 306 第一趟分配（按最低位 i = 3 ） re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9] 614 738 921 485 637 101 215 530 790 306 fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9] 第一趟收集 530 790 921 101 614 485 215 306 637 738 基数排序的“分配”与“收集”过程 第二趟 614 921 485 637 738 101 215 530 790 306 第二趟分配（按次低位 i = 2 ） re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9] 614 738 921 485 637 101 215 530 790 306 fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9] 第二趟收集 530 790 921 101 614 485 215 306 637 738 基数排序的“分配”与“收集”过程 第三趟 614 921 485 637 738 101 215 530 790 306 第三趟分配（按最高位 i = 1 ） re[0] re[1] re[2] re[3] re[4] re[5] re[6] re[7] re[8] re[9] 614 738 921 485 637 101 215 530 790 306 fr[0] fr[1] fr[2] fr[3] fr[4] fr[5] fr[6] fr[7] fr[8] fr[9] 第三趟收集 530 790 921 101 614 485 215 306 637 738 算法分析 若每个关键码有d 位，需要重复执行d 趟“分配”与“收集”。每趟对 n 个对象进行“分配”，对radix个队列进行“收集”。总时间复杂度为O ( d ( n+radix ) )。 若基数rad