7.9 利用链表和映射表进行排序 I

在采用基数排序和递归的归并排序时,得到的结果是使用链表存储的,但在某些情况下,必须对记录进行物理重排,使其按照所要求的顺序排列。

7.6 归并排序 中的 递归的归并排序的结果 为例,链表已排好序,且 start 指向包含最小关键字的记录,该记录的链域指向包含次小的关键字的记录,依此类推。为了把这些记录按照递增顺序进行物理重排,首先交换记录 R0R_0RstartR_{start},然后还要找到链域为 0 的记录,并把该记录的链域修改为 start。然后再把 start 改为指向记录 R0R_0 的链域指向的记录,再交换记录 R1R_1RstartR_{start}。经过 n1n - 1 次循环之后,就按升序顺序把链表物理重排了。由于每次执行交换后,都要根据记录的前驱结点重新进行链接,所以应该采用双向链表存储表示。函数 list_sort1 首先将单向链表转换为相应的双向链表,然后进行物理重排。调用方式为 list_sort1(list, n-1, start)

typedef struct {
    int key;
    int link;
    int linkb; // 前驱结点
} element;

void list_sort1(element list[], int n, int start)
{
    int i, last, current;
    element temp;

    last = -1;
    for (current = start; current != -1; current = list[current].link) {
        list[current].linkb = last;
        last = current;
    }
    for (i = 0; i < n-1; i++) {
        if (start != i) {
            if (list[i].link+1)
                list[list[i].link].linkb = start;
            list[lsit[i].linkb].link = start;
            SWAP(list[start], list[i], temp);
        }
        start = list[i].link;
    }
}

如果表中包含有 nn 个记录,那么将单向链表转换为双向链表的时间复杂度为 O(n)O(n)。第二个 for 循环才真正地开始重排记录。该循环重复执行 n1n - 1 次,在每次循环中交换的记录不超过两个,如果每个记录的大小为 mm,则每次交换的时间开销为 3m3m。因此,函数 list_sort1 的时间复杂度为 O(mn)O(mn)

与递归的归并排序的结果一样,假定输入序列为 26, 5, 77, 1, 61, 11, 59, 15, 48, 19。物理重排的过程如下:

排序后的链表:

start = 3

i 0 1 2 3 4 5 6 7 8 9
key 26 5 77 1 61 11 59 15 48 19
link 8 5 -1 1 2 7 4 9 6 0
linkb

双向链表:

start = 3

i 0 1 2 3 4 5 6 7 8 9
key 26 5 77 1 61 11 59 15 48 19
link 8 5 -1 1 2 7 4 9 6 0
linkb 9 3 4 -1 6 1 8 5 0 7

函数 list_sort1 第一个 for 循环后:

start = 1

i 0 1 2 3 4 5 6 7 8 9
key 1 5 77 26 61 11 59 15 48 19
link 1 5 -1 8 2 7 4 9 6 3
linkb -1 3 4 9 6 1 8 5 3 7

i = 2

start = 5

i 0 1 2 3 4 5 6 7 8 9
key 1 5 77 26 61 11 59 15 48 19
link 1 5 -1 8 2 7 4 9 6 3
linkb -1 3 4 9 6 1 8 5 3 7

i = 3

start = 7

i 0 1 2 3 4 5 6 7 8 9
key 1 5 11 26 61 77 59 15 48 19
link 1 5 7 8 5 -1 4 9 6 3
linkb -1 3 1 9 6 4 8 5 3 7

i = 4

start = 9

i 0 1 2 3 4 5 6 7 8 9
key 1 5 11 15 61 77 59 26 48 19
link 1 5 7 9 5 -1 4 8 6 7
linkb -1 3 1 5 6 4 8 9 7 7

i = 5

start = 7

i 0 1 2 3 4 5 6 7 8 9
key 1 5 11 15 19 77 59 26 48 61
link 1 5 7 9 7 -1 9 8 6 5
linkb -1 3 1 5 7 9 8 9 7 6

M.D.MacLaren 提出了一种特别有趣的变形算法,它不需要向前的链接指针。在这个变形算法中,把记录 RstartR_{start}RiR_i 交换后,把新的记录 RiR_i 的链接域设置为 start,以此来说明原来的记录已被移动。由于 start 总是 >= i,所以一定能正确地重排记录。该函数地调用方式为 list_sort2(list, n-1, start)

void list_sort2(element list[], int n, int start)
{
    int i, next;
    element temp;
    for (i = 0; i < n-1; i++) {
        while (start < i)
            start = list[start].link;
        next = list[start].link; // 保存次小关键字地索引

        if (start != i) {
            SWAP(list[i], list[start], temp);
            list[i].link = start;
        }
        start = next;
    }
}

在最坏情况下,函数 list_sort2 地时间复杂度也为 O(mn)O(mn)。但函数 list_sort2 要比 list_sort1 执行时间稍快。如下是同上输入序列的 list_sort2 处理过程:

start = 3

i 0 1 2 3 4 5 6 7 8 9
key 26 5 77 1 61 11 59 15 48 19
link 8 5 -1 1 2 7 4 9 6 0

i = 0

start = 1

i 0 1 2 3 4 5 6 7 8 9
key 1 5 77 26 61 11 59 15 48 19
link 3 5 -1 8 2 7 4 9 6 0

i = 1

start = 5

i 0 1 2 3 4 5 6 7 8 9
key 1 5 77 26 61 11 59 15 48 19
link 3 5 -1 8 2 7 4 9 6 0

i = 2

start = 7

i 0 1 2 3 4 5 6 7 8 9
key 1 5 11 26 61 77 59 15 48 19
link 3 5 5 8 2 7 -1 9 6 0

i = 3

start = 9

i 0 1 2 3 4 5 6 7 8 9
key 1 5 11 15 61 77 59 26 48 19
link 3 5 5 7 2 -1 4 8 6 0

i = 4

start = 0

i 0 1 2 3 4 5 6 7 8 9
key 1 5 11 15 19 77 59 26 48 61
link 3 5 5 7 9 -1 4 8 6 2

i = 5

start = 8

i 0 1 2 3 4 5 6 7 8 9
key 1 5 11 15 19 26 59 77 48 61
link 3 5 5 7 9 7 4 -1 6 2

i = 6

start = 6

i 0 1 2 3 4 5 6 7 8 9
key 1 5 11 15 19 26 48 77 59 61
link 3 5 5 7 9 7 8 -1 4 2

i = 7

start = 4

i 0 1 2 3 4 5 6 7 8 9
key 1 5 11 15 19 26 48 59 77 61
link 3 5 5 7 9 7 8 8 -1 2

i = 8

start = 2

i 0 1 2 3 4 5 6 7 8 9
key 1 5 11 15 19 26 48 59 61 77
link 3 5 5 7 9 7 8 8 9 -1

results matching ""

    No results matching ""