我正在阅读基数排序、计数排序和桶排序的定义，似乎它们都只是下面的代码：
public static void sort(int[] a, int maxVal){
int [] bucket=new int[maxVal+1];
for (int i=0; i<bucket.length; i++){
bucket[i]=0;
}
for (int i=0; i<a.length; i++){
bucket[a[i]]++;
}
int outPos=0;
for (int i=0; i<bucket.length; i++){
for (int j=0; j<bucket[i]; j++){
a[outPos++]=i;
}
}
}
我知道我可能是错的，那么我错在哪里？如果您认为展示Java或C代码有助于解释，请展示代码。
让我们从将您的代码改写成C语言开始，因为我更熟悉C语言并且能更好地解释。所以让我们通过一些注释来回忆一下您的代码：
int
counting_sort(int a[], int a_len, int maxVal)
{
int i, j, outPos = 0;
int bucket_len = maxVal+1;
int bucket[bucket_len]; /* simple bucket structure */
memset(bucket, 0, sizeof(int) * bucket_len);
/* one loop bucket processing */
for (i = 0; i < a_len; i++)
{
bucket[a[i]]++; /* simple work with buckets */
}
for (i=0; i < bucket_len; i++)
{
for (j = 0; j < bucket[i]; j++)
{
a[outPos++] = i;
}
}
return 0;
}
现在让我们给这个人提供一些真实的数据：
[126，348，343，432，316，171，556，223，670，201]
输出结果如下：
[126，171，201，223，316，343，348，432，556，670]
看起来一切都好了？还不够。让我们看一下maxVal。它是670（！）为了对10个元素的数组进行排序，我们使用了一个由主要是零的670个元素组成的数组。很糟糕。为了解决计数排序的这个问题，我们有两种可能的泛化方法：
1）第一种方法--逐位排序。这被称为基数排序。让我们展示一些代码，试图使它尽可能接近计数排序代码。再次查看注释：
int
radix_sort(int a[], int a_len, int ndigits)
{
int i;
int b[a_len];
int expn = 1;
/* additional loop for digits */
for (i = 0; i != ndigits; ++i)
{
int j;
int bucket[10] = {0}; /* still simple buckets */
/* bucket processing becomes tricky */
for (j = 0; j != a_len; ++j)
bucket[ a[j] / expn % 10 ]++;
for (j = 1; j != 10; ++j)
bucket[j] += bucket[j - 1];
for (j = a_len - 1; j >= 0; --j)
b[--bucket[a[j] / expn % 10]] = a[j];
for (j = 0; j != a_len; ++j)
a[j] = b[j];
expn *= 10;
}
}
我们正在将倍增器接近 N 的交易换成内存。利润？也许吧。但在某些情况下，倍增器接近 N 是非常重要的。即使两者都以 1*O(N) 和 7*O(N) 工作，从用户的角度来看，每天工作和每周工作是非常不同的。因此，我们得出了第二个概括：
2）第二种方法是使“桶”更为复杂。这被称为桶排序。
让我们再次从一些代码开始。我更喜欢在哲学论证之前先放更多代码。注意注释，它们是必不可少的。
int
bucket_sort(int a[], int a_len, int maxVal)
{
int i, aidx;
typedef struct tag_list {
int elem;
struct tag_list *next;
} list_t, *list_p;
list_p bucket[10] = {0}; /* sophisticated buckets */
/* one loop simple processing with one more inner loop
to get sorted buckets (insert-sort on lists, Cormen-style) */
for (i = 0; i != a_len; ++i)
{
int bnum = (10 * a[i]) / maxVal;
list_p bptr = bucket[bnum];
list_p belem = malloc(sizeof(list_t));
belem->elem = a[i];
if (bptr == 0)
{
bucket[bnum] = belem;
belem->next = 0;
continue;
}
else if (a[i] <= bptr->elem)
{
belem->next = bptr;
bucket[bnum] = belem;
continue;
}
else
{
while (bptr != 0)
{
if ((bptr->elem <= a[i]) && ((bptr->next == 0) || (bptr->next->elem > a[i])))
{
belem->next = bptr->next;
bptr->next = belem;
break;
}
bptr = bptr->next;
}
}
}
/* one loop (looks as two) to get all back */
aidx = 0;
for (i = 0; i != 10; ++i)
{
list_p bptr = bucket[i];
while (bptr)
{
list_p optr = bptr;
a[aidx] = bptr->elem;
aidx += 1;
bptr = bptr->next;
free(optr);
}
}
return 0;
}
那么我们在这里有什么？我们交易一些复杂的桶结构和对动态分配内存的要求，但赢得了静态内存和近似于N的乘数。
现在让我们回想一下在代码中看到了什么：
因此，基数排序和桶排序是计数排序的两种有用的泛化。它们与计数排序和彼此都有很多共同之处，但在每种情况下，我们都会失去一些东西并赢得一些东西。软件工程是在这些机会之间取得平衡的。
据Geekviewpoint称：
基数排序： http://www.geekviewpoint.com/java/sorting/radixsort
基数排序、计数排序和桶排序一样，是一种基于整数的算法（即假定输入数组的值为整数）。因此，基数排序在理论上是最快的排序算法之一。基数排序的特别之处在于它为每个密码（即数字）创建一个桶；因此，类似于桶排序，基数排序中的每个桶都必须是一个可增长的列表，可以接受不同的键。
桶排序：http://www.geekviewpoint.com/java/sorting/bucketsort
考虑到计数排序是其上限，桶排序实际上非常好。而计数排序速度非常快。桶排序的特别之处在于它使用哈希函数将输入数组的键分区，以便多个键可能散列到同一个桶中。因此，每个桶必须有效地是一个可增长的列表；与基数排序类似。
计数排序：http://www.geekviewpoint.com/java/sorting/countingsort
计数排序的特别之处在于它为每个值创建一个桶，并在每个桶中保持一个计数器。然后，每次在输入集合中遇到一个值时，适当的计数器就会增加。因为计数排序为每个值创建一个桶，所以强加的限制是必须事先知道输入数组中的最大值。
他们在网站上提供了更详细的解释。
编辑：
如果您使用基数排序且数字是十进制数，则需要10个桶，一个桶用于存储0到9的每个数字。
如果你正在使用计数排序，那么你需要为输入中的每个唯一值准备一个桶（实际上你需要为0到最大值之间的每个值都准备一个桶）。
如果你正在使用桶排序，那么你不知道会用到多少个桶。无论你使用什么哈希函数，它都将确定桶的数量。
你的代码是一个简单的基于键值而不是数据的计数排序。
基数排序是基于这种方法的排序。计数排序的问题在于内存需求：int [] bucket=new int[maxVal+1];。基数排序解决了这个问题。它的思想是多次使用计数排序，首先用于低位数字，然后用于高位数字。例如，要对32位整数进行排序，可以使用以下方式：
sort(a, 65535) using lower half as key
sort(a, 65535) using higher half as key
按B排序;按A排序，让您按A排序的元素，并在A相等时按B排序。(0,1)）的实数进行排序。其想法是使用计数排序（使用floor(x*N_BUCKETS)作为键），然后仅独立地对每个桶进行排序。 bucket sort(L)
{
list Y[k+1]
for (i = 0; i <= k; i++) Y[i] = empty
while L nonempty
{
let X = first record in L
move X to Y[key(X)]
}
for (i = 0; i <= k; i++)
concatenate Y[i] onto end of L
}
radix sort(L):
{
bucket sort by a
bucket sort by b
bucket sort by c
...
}
radix sort(L):
{
while (some key is nonzero)
{
bucket sort(keys mod 10)
keys = keys / 10
}
}
http://htmltolatex.sourceforge.net/samples/sample4.html
第一个回答：桶排序和基数排序有什么区别？
基数排序使用计数排序作为子程序（可以使用，但通常会是计数排序）。
计数排序是桶排序的一种特殊形式，正如kasavbere所回答的那样。
而桶排序将键分成桶，然后逐个对桶进行排序。
#define MAX_INPUT 1000
void sort(int arr[100], int n)
{
static int hash[MAX_INPUT], i, j;
memset(hash, 0, sizeof hash);
for (i = 0; i < n; ++i) ++hash[arr[i]];
j = 0;
for (i = 0; i < MAX_INPUT; ++i)
while (hash[i]--)
arr[j++] = i;
}
这只是O(MAX_INPUT)，因此可以在线性时间内排序。对于桶排序，情况则非常不同。这里有一个实现
基数排序、计数排序和桶排序有什么区别？ - amit
else if (a[i] <= bptr->elem)中的比较应该是<。另外，while (bptr != 0)可以改为while (true)。 - Powereleven