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

Question

在处理" BrainF***的最快排序"时,我发现了这个算法,它是O(N*k),其中k是输入中的最大值.它需要额外的O(N)存储空间.

物理类比是你有N堆令牌.堆栈的高度表示要排序的值.(每个标记代表一点).留出另外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);
 }

这个算法有名字吗？它似乎类似于珠子排序,但我不认为它是完全相同的.

Answer 1

原来我毕竟不是太懒.这是珠子排序.这是原始论文的定义(PDF链接):

考虑一套一的ñ正整数...对于所有的一个在甲下降一个沿杆珠(每杆一个珠)中,从第一杆与起始一个 "个杆.最后,逐级地从第n级到第一级看到的珠子以升序表示A.

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

1. 反映它在线上工作的"框架" y=x.这会更改结果,使每列中的"珠子"数表示按降序排序的输出.在原始算法中,每行中"珠子"的数量表示按升序排序的输出.
2. 而不是将"框架"表示为布尔值的二维数组,而是将其表示为整数的一维数组.阵列中的每个槽对应一个"杆",其值代表该杆上的珠子数量.第二位是一种自然的转变 - 它只是承认,因为"珠子"不能漂浮在半空中,只记​​录杆上的珠子数量告诉我们所有人都应该知道它们是如何排列在它上面的.您可以通过增加相应的数字将珠子放在杆上.

以下是第一点的一些说明,直接来自论文第二页的图表:由于算法最初实现,数组[3,2,4,2]将由一个网格表示,如下所示:

* * *
* *
* * * *
* *

让珠子掉落产生:

* *
* *
* * *
* * * *

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

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