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 回答