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

When working on "The fastest sort for BrainF***", I discovered this algorithm, which is O(N*k), where k is the maximum value in the input. It requires O(N) extra storage.

物理类比是，你必须标记N个堆栈。堆栈再$ P $的高度psents要排序的值。 （每个令牌再presents位）。预留空间，另外N堆栈。你把一个令牌关闭每个堆叠具有令牌的顶部，然后在新的一组从右边添加一个到每个堆叠向左直到你的手是空的。重复，直到所有原堆栈是空的。从左到右现在新集升序排列

The physical analogy is that you have N stacks of tokens. The height of the stack represents the value to be sorted. (Each token represents a bit). Set aside space for another N stacks. You take one token off the top of each stack that has tokens, and then add one to each stack in the new set from right to left until your hand is empty. Repeat until all original stacks are empty. Now the new set is sorted ascending left to right

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

请问这个算法有名字吗？这似乎类似于珠排序，但我不认为这是完全一样的。

Does this algorithm have a name? It seems similar to a Bead Sort, but I don't think it's quite the same.

推荐答案

原来我毕竟不是太懒惰。这是珠排序。下面是来自原件（PDF链接）的定义：

Turns out I wasn't too lazy after all. It is Bead Sort. Here's the definition from the original paper (PDF link):

审议一系列的 A 的 N 的正整数。 。 。     对于所有的在的中的 A 下拉的在的珠子（每杆一个珠子）沿杆，从第一棒开始了的一的'个棒。最后，珠子，逐级看到的水平，从* N *次级别的第一级，再present的 A 升序进行排序。

Consider a set A of n positive integers. . . For all a in A drop a beads (one bead per rod) along the rods, starting from the 1st rod to the a'th rod. Finally, the beads, seen level by level, from the *n*th level to the first level, represent A in ascending order.

本实施转换两种方式的算法：

This implementation transforms that algorithm in two ways:

反映框架中，它的跨线 Y = X 工作。这改变了结果，使得在重新$ P $各列'珠的数目psents输出按降序排序。在原来的算法，每行重新$ P $的'珠'的数量psents输出按升序排序。 ，而不是重新presenting的框架的布尔值的2维阵列，重新present它作为一维整数数组。阵列中的每个时隙对应于一个杆，它的值重新presents的上杆小珠的数量。这第二位是一个自然的转变 - 它只是承认，由于珠不能漂浮在半空中，录音珠刚上杆告诉我们所有有了解它们是如何安排它的数目。你通过增加相应的数字放在一杆珠。 Reflect the 'frame' in which it's working across the line y=x. This changes the result such that the number of 'beads' in each column represents the output sorted in descending order. In the original algorithm, the number of 'beads' in each row represents the output sorted in ascending order. Rather than representing the 'frame' as an 2-dimensional array of boolean values, represent it as a 1-dimensional array of integers. Each slot in the array corresponds to a 'rod', and its value represents the number of beads on that rod. This second bit is a natural transformation - it simply acknowledges that, since a 'bead' cannot float in mid-air, recording just the number of beads on the rod tells us all there is to know about how they are arranged on it. You place a bead on a rod by incrementing the corresponding number.

下面是一些澄清该第一点，从图中直的所采取的纸张的第二页上：随着算法的最初实现的，该阵列[3，2，4，2]将重新由网格psented $ P $看起来像：

Here's some clarification on that first point, taken straight from the diagram on the paper's second page: As the algorithm is originally implemented, the array [3, 2, 4, 2] would be represented by a grid that looks like:

* * *
* *
* * * *
* *

和让球落下产生的：

* *
* *
* * *
* * * *

您接下来要读取行，从上到下，得到输出：2，2，3，4]。而在这给出的结果降序排列的版本，您实际上这样做，而不是：

You then have to read the rows, from top to bottom, to get the output: [2, 2, 3, 4]. Whereas in the version that gives results in descending order, you are effectively doing this instead:

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