1

我一直在阅读 Donald Knuth 第二版的计算机编程艺术第 3 卷中的排序和搜索算法。我在第 95 页遇到了 Knuth 称之为“列表插入”（传统插入排序的一种修改）的算法。

在该页面上，Knuth 得出结论，“直接插入的正确数据结构是单向链接线性列表。”并且“链接分配（第 2.2.3 节）非常适合插入，因为只需要几个链接要改变。” 但是，第 97 页的 MIXAL 程序（程序 L）似乎没有利用传统的链表结构（一系列由地址链接的节点）。相反，键和链接似乎一起存储在一个类似结构的结构中，这些结构存储在一个名为INPUT.

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

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

列表插入说明

列表插入 MIXAL 实现

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;
}
4

1 回答 1

1

我建议你先用 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;
  }
}

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

于 2017-10-20T08:10:41.613 回答