algorithm - 基数排序 vs 计数排序 vs 桶排序。有什么不同？

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]

关于输出我们有

[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 附近的乘数非常重要。程序、一天工作和一周工作与用户 View 有很大不同，即使两者分别工作 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。

现在让我们记忆一下我们在代码中看到了什么:

1. 计数排序——简单的桶，简单的处理，内存开销
2. 基数排序——简单的桶、复杂的处理、速度开销(并且仍然需要额外的静态内存)
3. 桶排序——桶复杂，处理简单，需要动态内存，一般情况下不错

因此，基数排序和桶排序是计数排序的两个有用的概括。它们与计数排序以及彼此之间有很多共同点，但在每种情况下，我们都会失去一些东西并赢得一些东西。软件工程就是要在这些机会之间取得平衡。