algorithm - 这个 O(N*k) 排序算法是什么？

Question

在处理“The fastest sort for BrainF***"”时，我发现了这个算法，它是 O(N*k)，其中 k 是输入中的最大值。它需要 O(N) 的额外存储空间。

物理类比是你有 N 叠代币。堆栈的高度表示要排序的值。 (每个 token 代表一个位)。为另外 N 个栈留出空间。您从每个有标记的堆叠的顶部取出一个标记，然后从右到左向新组中的每个堆叠添加一个标记，直到您的手是空的。重复直到所有原始堆栈都为空。现在新集合从左到右升序排列

在 C 中:

 void sort(int A[], int N)
 {
    int *R = calloc(N,sizeof(int));
    do {
      int i,count=0; 
      for (i=0;i<N;i++) if A[i] { count++; A[i]--;}
      for (i=0;i<count;i++) R[i]++;
    } while (count);
    memcpy(A,R,N);  //A is now sorted descending.
    free(R);
 }

这个算法有名字吗？它看起来类似于 Bead Sort ，但我认为这并不完全相同。

Answer 1

原来我并不是太懒惰。这是珠排序。这是来自 original paper 的定义(PDF 链接):

Consider a set A of n positive integers. . . For all a in A drop a beads (one bead per rod) along the rods, starting from the 1st rod to the a'th rod. Finally, the beads, seen level by level, from the nth level to the first level, represent A in ascending order.

此实现以两种方式转换该算法:

1. 反射(reflect)它在 y=x 行中工作的“框架”。这会更改结果，使每列中的“珠子”数量代表按降序排序的输出。在原始算法中，每行中“珠子”的数量表示按升序排序的输出。
2. 与其将“框架”表示为 bool 值的二维数组，不如将其表示为一维整数数组。数组中的每个槽对应一个“杆”，其值代表该杆上珠子的数量。第二位是自然转换——它只是承认，因为“珠子”不能漂浮在半空中，记录杆上珠子的数量就可以告诉我们所有关于珠子在杆上的排列方式的信息。您可以通过增加相应的数字来将珠子放在杆上。

这里是对第一点的一些澄清，直接取自论文第二页的图表:由于最初实现了算法，数组 [3, 2, 4, 2] 将由如下所示的网格表示:

* * *
* *
* * * *
* *

让珠子掉落会产生:

* *
* *
* * *
* * * *

然后您必须从上到下读取行以获得输出:[2, 2, 3, 4]。而在按降序给出结果的版本中，您实际上是在这样做:

  *          *
  *   *      * *
* * * *  ->  * * * *
* * * *      * * * *