非序 (8)二路归并排序 采用迭代的方法进行归并排序。设待排序的数据对象有n个。首先把每一个待排序的数 据对象看作是长度为的初始归并项,然后进行两两归并,形成长度为2的归并项,再对它们 两两归并,形成长度为4的归并项,如此一趟一趟做下去,最后得到长度为n的归并结果。 排序码比较5次 21216301028 2[6 排序码比较6次 1216301[01620281[618 排序码比较7次 210121616202830 排序码比较9次 2610121616·182 (9)基数排序 [2}[16}-[30}[28}[10}[16}[20}[ 按最低位分配 r[]r[2]rB]4]f]r]r7r[8r9 16 [o f 1 f2 f3 f4 f5 f6 f7 f8 f9 收集[30}[10[20}-[12}[2}[16}-[16}[6}[28}[8 按最高位分配 r[o r[ 2]r[r4]rr6]t[7r8]r19 0]t1 2]134]ft6]7f8]t9 收集[2[6[10[12[6}[16-}[18}[20-28}[30 9-3在起泡排序过程中,什么情况下排序码会朝向与排序相反的方向移动,试举例说明。在 快速排序过程中有这种现象吗? 【解答】 如果在待排序序列的后面的若干排序码比前面的排序码小,则在起泡排序的过程中,排 序码可能向与最终它应移向的位置相反的方向移动。例如,第 9 章 排序 8 (8) 二路归并排序 采用迭代的方法进行归并排序。设待排序的数据对象有 n 个。首先把每一个待排序的数 据对象看作是长度为的初始归并项，然后进行两两归并，形成长度为 2 的归并项，再对它们 两两归并，形成长度为 4 的归并项，如此一趟一趟做下去，最后得到长度为 n 的归并结果。 (9) 基数排序 收集 按最高位分配 收集 9-3 在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在 快速排序过程中有这种现象吗？ 【解答】 如果在待排序序列的后面的若干排序码比前面的排序码小，则在起泡排序的过程中，排 序码可能向与最终它应移向的位置相反的方向移动。例如， 12 2 16 30 28 10 16* 20 6 18 2 12 16 30 10 28 16* 20 12 6 18 2 12 16 30 10 16* 20 28 6 18 2 10 12 16 16 6 18 * 20 28 30 2 6 10 12 16 16* 18 20 28 30 12 2 16 30 28 10 16* 20 6 18 按最低位分配 r[0] r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 12 2 30 16 28 10 16* 20 6 18 30 10 20 12 2 16 16* 6 28 18 r[0] r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 18 16* 16 12 2 10 20 30 6 28 16* 2 6 10 12 16 18 20 28 30 排序码比较 5 次 排序码比较 6 次 排序码比较 7 次 排序码比较 9 次