基数排序vs计数排序vs Bucket排序。有什么关系呢？

Question

我正在阅读基数、计数和存储桶排序的定义，它们似乎都只是下面的代码：

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解释，请显示代码。

Answer 1

让我们从用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

在输出上，我们有

好像一切都还好吧？还没。让我们来看看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附近的乘数是非常重要的。程序，工作一天和一周工作与用户的看法有很大的不同，即使这两个工作分别是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;
}

那么我们这里有什么呢？

现在让我们回顾一下我们在代码中看到了什么：

1. 计数排序--简单存储桶，简单处理，内存开销
2. 基数排序--简单存储桶，复杂处理，速度开销(仍然需要额外的静态内存)
3. 存储桶排序--复杂存储桶，简单处理，需要动态内存，适合平均

基数排序和桶排序是计数排序的两个有用的推广。软件工程就是在这些机会之间取得平衡。

Answer 2

基数排序vs计数排序vs桶排序。有什么关系呢？

存储桶排序将要排序的键或元素放入存储桶中。它们在存储桶中的放置方式是任意的，可以是组合键的一部分，也可以是您喜欢的任何分布。各个存储桶可能需要进一步排序。

在内存中排序比在磁盘上排序更快。但是，如果您的数据超过了内存的容量，那么您需要另一个选择。您可以做的是存储桶排序，其中存储桶足够小，可以放入内存中。即在每个桶中有大量条目。您可以分别快速地对这些内容进行排序。

基数排序是存储桶排序的一种特定类型。它从最高的n位或n位开始，并且可以使用基数排序等对这些桶进行排序，直到每个条目都被排序为止。

计数排序类似于使用基数排序，但使用的是整数值。它没有记录每个对象，而是每个对象都有一个存储桶，它只计算出现的次数。当您有有限数量的可能密钥，并且有许多重复的密钥时，这种方法效果很好。

Answer 3

根据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和最大值之间的每个值提供一个存储桶)。
• 如果您使用存储桶排序，您不知道将使用多少个存储桶。无论您使用什么哈希函数，都将确定存储桶的数量。