c - C语言中的Knuth列表插入方法

我一直在阅读唐纳德·克努特（Donald Knuth）的《计算机编程艺术》（Art of Computer Programming）第三卷第二版中的排序和搜索算法。我在第95页遇到了一个Knuth称之为“列表插入”（对传统插入排序的修改）的算法。
在那一页上，Knuth总结道，“直接插入的正确数据结构是一个单向的链式线性列表。”，并且“链式分配（第2.2.3节）非常适合插入，因为只需要更改几个链接。”，第97页上的MIXAL程序（程序L）似乎没有使用传统的链式线性列表结构（由地址链接的一系列节点）。相反，键和链接似乎存储在一个类似结构的结构中，这些结构存储在一个名为INPUT的数组中。
我决定尝试用C语言实现这个算法，我提供了Knuth对算法的描述，以及他在混合汇编语言中的实现作为参考。我决定让键成为data数组中的元素，它们自己，并将链接放入一个类似于并行数组的links中。我之所以说“类并行数组”，是因为links数组的大小比data数组的大小大一倍。我这样做是为了通过将其存储为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;
}

最佳答案

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

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 - C语言中的Knuth列表插入方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46842353/