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