O（N * k）排序算法是什么？

一尘不染

O（N * k）排序算法是什么？

algorithm

在研究“ 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);
 }

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

阅读 317

2020-07-28

共1个答案

一尘不染

原来我一点也不懒。这是珠子排序。这是原始论文的定义（PDF链接）：

考虑由 n个正整数组成的集合 A。* 。。对于所有的一个在甲下降一个沿杆珠（每杆一个珠）中，从第一杆与起始
一个 “个杆。最后，从第 n 个层级到第一个层级逐级观察的珠子按升序表示 A。 __ ***

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

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

以下是关于第一点的一些说明，直接从论文第二页的图表中可以得出：由于算法最初被实现，因此数组[3，2，4，2]将由一个网格表示，如下所示：

* * *
* *
* * * *
* *

而让珠子掉落会产生：

* *
* *
* * *
* * * *

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

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

2020-07-28