7.10 利用链表和映射表进行排序 II

对于堆排序而言,堆的顺序表示是进行哦嗲是操作的基础。利用辅助表来对表中的记录进行间接引用,就可以消除排序过程中不必要的数据移动。辅助表定义为 int table[MAX_SIZE],在下面的分析中用 tt 来表示。在排序开始时,t[i]=i(0in1)t[i] = i (0 \leq i \leq n-1)。如果排序算法需要交换记录 RiR_iRjR_j,则交换表中的 t[i]t[i]t[j]t[j],而原来的表无需改变。排序后的表为 Rt[0],Rt[1],,Rt[n1]R_{t[0]}, R_{t[1]}, \cdots, R_{t[n-1]}。即 Rt[0]R_{t[0]} 中存放的是关键字最小的记录,Rt[n1]R_{t[n-1]} 中存放的是关键字最大的记录。

利用映射表进行排序

与排列 t[0],t[1],,t[n1]t[0], t[1], \cdots, t[n-1] 相对应的记录重排算法是以下数学定理的一个相当有趣的应用:每个排列都由若干个互不相交的循环组成。任意元素 ii 的循环由元素 t[i],t2[i],,tk[i]t[i], t^2[i], \cdots, t^k[i] 组成,其中 tj[i]=t[tj1[i]]t^j[i] = t[t^{j-1}[i]],且 t0[i]=it^0[i] = itk[i]=it^k[i] = i。如上图有两个环组成:t[0]=4t[0] = 4t[4]=0t[4] = 0,包含 R0R_0R4R_4,第二个环 t[1]=3,t[3]=2,t[2]=1t[1] = 3, t[3] = 2, t[2] = 1,包含 R3,R2R_3, R_2R1R_1。函数 table_sort 使用排列的循环分解。首先,考察包含记录 R0R_0 的循环并把包含 R0R_0 的循环的所有记录都移到正确的位置上。然后,如果 R1R_1R0R_0 不在同一个循环中,则考察包含记录 R1R_1 的循环排列。再按上述方式依次检查包含 R2,R3,,Rn2R_2, R_3, \cdots, R_{n-2} 的循环。结果就得到表的物理排序。

void table_sort(element list[], int n, int table[])
{
    // 重排 list[0], ..., list[n-1] 对应于 list[table[0]] ,..., list[table[n-1]]
    int i, current, next;
    element temp;
    for (i = 0; i < n-1; i++)
        if (table[i] != i) {
            temp = list[i];
            current = i;
            do {
                next = table[current];
                list[current] = list[next];
                table[current] = current;
                current = next;
            } while (table[current] != i);
            list[current] = temp;
            table[current] = current;
        }
}

上述“循环”分为平凡的和非平凡的,平凡的循环是满足条件 t[i]=it[i] = i 的记录 RiR_i,已经放置在正确的位置上,不必重新排列。非平凡的循环,即满足 t[i]it[i] \neq i 的记录 RiR_i,需要移动至正确的位置上。如果每个记录所需的存储空间为 mm,总的移动次数最大的情况是每个记录都在非平凡循环上,且有 n/2\lfloor n/2 \rfloor 个循环。当 nn 为偶数时,每个循环包含 2 个记录。否则,其中一个循环包含 3 个记录,而其余的循环都包含 2 个记录。在这两种情况下,记录移动的总次数都是 3n/2\lfloor 3n/2 \rfloor。又由于每次记录移动的时间开销都是 O(m)O(m),所以总的计算时间为 O(mn)O(mn)

例如处理下列这些已找到映射关系的排序:

RR R0R_0 R1R_1 R2R_2 R3R_3 R4R_4 R5R_5 R6R_6 R7R_7
key 35 14 12 42 26 50 31 18
table [0] [1] [2] [3] [4] [5] [6] [7]
value 2 1 7 4 6 0 3 5

经过第一次循环重新排列后表的状态(重新排列第一个循环 R0,R2,R7,R5,R0R_0, R_2, R_7, R_5, R_0):

RR R0R_0 R1R_1 R2R_2 R3R_3 R4R_4 R5R_5 R6R_6 R7R_7
key 12 14 18 42 26 35 31 50
table [0] [1] [2] [3] [4] [5] [6] [7]
value 0 1 2 4 6 5 3 7

经过第二次循环重新排列后表的状态(重新排列第二个循环 R3,R4,R6,R3R_3, R_4, R_6, R_3):

RR R0R_0 R1R_1 R2R_2 R3R_3 R4R_4 R5R_5 R6R_6 R7R_7
key 12 14 18 26 31 35 42 50
table [0] [1] [2] [3] [4] [5] [6] [7]
value 0 1 2 3 4 5 6 7

results matching ""

    No results matching ""