C中的Knuth列表插入方法

Question

我一直在通读 Donald Knuth 所著的计算机编程艺术第 3 卷中的排序和搜索算法，第二版。我在第 95 页遇到了 Knuth 称为 "list insertion"（对传统插入排序的修改）的算法。

在那一页上，Knuth 得出结论 "right data structure for straight insertion is a one-way, linked linear list."，并且 "linked allocation (Section 2.2.3) is ideally suited to insertion, since only a few links need to be changed." 然而，第 97 页的 MIXAL 程序（程序 L）似乎没有使用传统的 link ed 线性列表结构（一系列节点 link 按地址编辑）。相反，密钥和 link 似乎一起存储在类似结构的结构中，这些结构存储在名为 INPUT 的数组中。

我决定尝试用 C 语言实现这个算法。我提供了 Knuth 对算法的描述，以及他在 MIXAL 汇编语言中的实现作为参考。我决定让键成为 data 数组中的元素本身，并将 link 放在一个名为 links 的类并行数组中。我说 'parallel-like array' 是因为 links 数组的大小比 data 数组的大小大 1。我这样做是为了通过将 data 数组的最小元素存储为 links 数组中的第一个元素来轻松确定它的索引。由于 links 中的这个额外索引，data 数组的索引 0 - (n - 1) 对应于 links 数组的索引 1 - n。 links 数组中的每个元素对应于排序列表中下一个元素的 data 数组中的索引。

我的问题是，根据他的描述，这个算法应该如何实现，还是我遗漏了什么？

int *listInsertion(int data[], int n) {

    if (n > 1) {
        int i, j, entry;
        int *links = (int *) calloc(n + 1, sizeof *links);
        links[n] = -1;
        links[n - 1] = n - 1;

        for (i = n - 2; i >= 0; i--) {
            entry = data[i];
            for (j = i + 1; links[j] >= 0 && entry > data[links[j]]; 
                    j = links[j] + 1)
                continue;

            if (j == i + 1) {
                links[i] = i;
            } else {
                links[i] = links[i + 1];
                links[i + 1] = links[j];
                links[j] = i;
            }
        }
        return links;
    }
    return NULL;
}

Answer 1

建议你先用Knuth提到的symbol实现算法
这将帮助您快速找出第一个版本。

void insertSort(const int *K, int *L, int n) {
  if (n == 1) return;

  L[n] = n-1; 
  L[n-1] = n;

  for (int j = n-2; j >= 0; j--) {
    int entry = K[j];
    int p = L[n];
    int q = n;

    while(entry > K[p]) {
      q = p;
      p = L[q];
      if (p == n) {
        break;
      }
    }

    L[q] = j;
    L[j] = p;
  }
}

然后您可以重构您的第一个版本以增强或缩短它。

C中的Knuth列表插入方法

Knuth List Insertion Method in C

c

taocp

knuth

insertion-sort