5

在研究“ 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,但我认为它并不完全相同。

4

2 回答 2

7

事实证明,我毕竟不是太懒惰。这是珠排序。这是原始论文的定义(PDF链接):

考虑一个由n 个正整数组成的集合A。. . 对于A中的所有a,从第 1 个杆开始到第a个杆,沿杆滴下一个珠子(每杆一个珠子)。最后,逐层看的珠子,从第n级到第1级,按升序代表A。

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

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

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

* * *
* *
* * * *
* *

让珠子落下会产生:

* *
* *
* * *
* * * *

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

  *          *
  *   *      * *
* * * *  ->  * * * *
* * * *      * * * *
于 2012-01-26T18:25:22.000 回答
0

我知道基数排序是 O(n*K) 复杂度中的一个代表。

http://en.wikipedia.org/wiki/Radix_sort

于 2012-01-26T15:24:16.313 回答