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

当工作“BrainF*** 最快的排序”，我发现了这个算法，它是O(N*k)，其中k是输入中的最大值。它需要 O(N) 额外的存储空间。

物理上的类比是你有 N 堆令牌。栈的高度代表要排序的值。 （每个标记代表一个位）。为另外 N 堆留出空间。您从每个有令牌的堆栈顶部取出一个令牌，然后从右到左向新一组中的每个堆栈添加一个令牌，直到您的手空了。重复此操作，直到所有原始堆栈都为空。现在新集合按从左到右升序排序

In 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);
 }

这个算法有名字吗？看起来类似于一个珠子排序，但我认为这并不完全相同。

原来我还不算太懒。这是珠排序。这是来自的定义原纸（PDF链接）：

考虑一组A of n正整数。 。 。 对全部a in A drop a珠子（每杆一颗珠子）沿着杆，从第一个杆开始到第一个杆a第三根杆。最后，珠子，一层一层地从n第 1 级到第 1 级，分别代表A按升序排列。

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

1. 反映它在其中跨线工作的“框架”y=x。这会更改结果，使得每列中的“珠子”数量代表按降序排序的输出。在原始算法中，每行中“珠子”的数量代表按升序排序的输出。
2. 不要将“框架”表示为布尔值的二维数组，而是将其表示为整数的一维数组。数组中的每个槽对应一个“棒”，其值代表该棒上的珠子数量。第二位是一个自然的转变 - 它只是承认，由于“珠子”不能漂浮在半空中，仅记录杆上珠子的数量就可以告诉我们所有关于它们如何排列在杆上的信息。通过增加相应的数字，可以将珠子放在杆上。

以下是对第一点的一些澄清，直接取自论文第二页上的图表：在算法最初实现时，数组 [3, 2, 4, 2] 将由一个网格表示，如下所示：

* * *
* *
* * * *
* *

让珠子落下会产生：

* *
* *
* * *
* * * *

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

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