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

标签 c insertion-sort knuth taocp

我一直在通读 Donald Knuth 所著的计算机编程艺术第 3 卷(第二版)中的排序和搜索算法。我在第 95 页上遇到了一种被 Knuth 称为“列表插入”(对传统插入排序的修改)的算法。

在那一页上,Knuth 得出结论,“直接插入的正确数据结构是单向链接线性列表”,并且“链接分配(第 2.2.3 节)非常适合插入,因为只有一个很少有链接需要更改。”然而,第 97 页的 MIXAL 程序(程序 L)似乎没有使用传统的线性链表结构(一系列由地址链接的节点)。相反, key 和链接似乎一起存储在类似结构的结构中,并且这些结构存储在名为 INPUT 的数组中。

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

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

list insertion description

list insertion MIXAL implementation

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/

相关文章:

c - 为什么 write() 终止我的线程?

c - 我无法使用toupper()将我的代码打印为我的一个数组中所有大写字母的用户输入。

java - ArrayLinkedList 插入排序

string-matching - KMP失效函数计算

c - 当我们不知道确切的单词数和单词长度时,如何以最有效的方式为 char** 分配内存?

C Pthreads 互斥值?

java - 为什么这种插入排序方法会给出错误的输出?

python - Python 中的插入排序

algorithm - Knuth 的算法 X,用于 block 大小受限的精确覆盖

math - 快速计算(a * b)mod c,其中c = 2 ^ N + -1