我正在阅读基数、计数和桶排序的定义，似乎所有这些都只是下面的代码：
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 的乘数。
现在让我们回忆一下我们在代码中看到的内容：
因此，基数和桶排序是计数排序的两个有用的概括。它们与计数排序和彼此有很多共同点，但在每种情况下，我们都在失去一些东西并赢得一些东西。软件工程是关于这些机会之间的平衡。
基数排序 vs 计数排序 vs 桶排序。有什么不同？
桶排序将要排序的键或元素放入桶中。它们如何放置在存储桶中是任意的，可以是复合键的一部分，也可以是您喜欢的任何分布。各个桶可能需要进一步分类。
在内存中排序比在磁盘上排序更快。但是，如果您的数据超出内存容量，则需要另一种选择。您可以做的是桶排序，其中桶足够小以适合内存。即每个桶中有大量的条目。这些您可以单独快速排序。
基数排序是一种特定类型的桶排序。它从前 n 位或 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
它可以工作，因为计数排序是稳定的 - 它使用相同的键保持数据的顺序。这就像在电子表格中排序：sort by B; sort by A为您提供按 A 排序的元素，当 As 相等时按 B 排序。
桶排序是计数排序的推广。您可以使用它从一些可预测的概率分布（例如 uniform (0,1)）中对实数进行排序。这个想法是使用计数排序（使用floor(x*N_BUCKETS)作为键），然后只对每个桶进行独立排序。
首先让我们看看基数排序和桶排序之间的区别，因为这通常是一个令人困惑的事情，因为想法似乎相同。然后我们看一下计数排序，它就像这两个的主要版本，计数排序的哪些问题导致使用其他两个
Radix 和 Bucket 排序的初始传递是相同的。元素放在“Buckets”中，即 0-10、11-20、...等，取决于最大编号中的位数，即基数。然而，在下一轮中，桶排序将这些“桶”排序并将它们附加到一个数组中。但是，基数排序方法在不进一步排序的情况下附加存储桶，并根据数字的第二个数字（十位）“重新存储桶”。因此，桶排序对“密集”数组更有效，而基数排序可以很好地处理稀疏数组。好吧，把桶排序想象成这样
假设您有一个包含 n 条记录的列表，每条记录的键都是从 1 到 k 的数字（我们稍微概括一下问题，因此 k 不一定等于 n）。
我们可以通过创建一个链表数组来解决这个问题。我们将每个输入记录移动到数组适当位置的列表中，然后按顺序将所有列表连接在一起。
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
}
k很大时怎么办？想想数字 x = a + 10 b + 100 c + 1000 d + ... 的十进制表示，其中 a、b、c 等都在 0..9 范围内。这些数字很容易小到可以进行桶排序。
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
}
}
为什么我们先做最不重要的数字？就此而言，为什么我们要做不止一个桶排序，因为最后一个是把所有东西都放在适当位置的那个？回答：如果我们尝试手动排序，我们倾向于做一些不同的事情：首先进行桶排序，然后递归地对共享第一个数字的值进行排序。这可行，但效率较低，因为它将问题分解为许多子问题。相比之下，基数排序永远不会拆分列表。它只是将桶排序多次应用于同一个列表。在基数排序中，桶排序的最后一次是对整体顺序影响最大的一次。所以我们希望它是使用最重要数字的那个。之前的桶排序通过仅用于处理两个项目在最后一次通过时具有相同键（mod 10）的情况。
现在我们已经解决了所有计数排序的问题，它保留了一个包含 k 个元素的辅助数组 C，所有元素都初始化为 0。
我们遍历输入数组 A，对于我们看到的 A 中的每个元素 i，我们将 C[i] 增加 1。在遍历 A 的 n 个元素并更新 C 之后，C 的索引 j 处的值对应j 在 A 中出现了多少次。这一步需要 O(n) 时间来迭代 A。一旦我们有了 C，我们就可以通过迭代 C 并将每个元素 ja 插入 C[j] 来构造 A 的排序版本次进入一个新列表（或 A 本身）。遍历 C 需要 O(k) 时间。最终结果是排序的 A，总共需要 O(n + k) 时间。
计数排序的缺点是如果元素的范围太大，它可能不太实用。例如，如果我们需要排序的 n 个元素的范围是从 1 到 n 3 ，那么简单地创建辅助数组 C 将花费 O(n^3) 时间，并且计数排序会渐近地比插入排序更差。这也占用了 O(n^3) 空间，这比我们迄今为止学习的任何其他排序算法使用的任何空间都要大得多。基数排序通过逐位排序元素来帮助解决这个问题
注意：答案和进一步阅读的来源：
http://htmltolatex.sourceforge.net/samples/sample4.html
第一个答案：桶排序和基数排序有什么区别？
基数排序使用一种计数排序形式作为子程序（好的，可以使用，但最常见的是计数排序）。
正如 kasavbere 所回答的那样，计数排序是一种特殊形式的桶排序。
Bucketsort 将键分成桶，然后对桶进行单独排序。
使用计数排序对数组进行排序：
#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)，因此按线性时间排序。对于桶排序，这是非常不同的。这是一个实现