基数排序与计数排序与桶排序.有什么不同？

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附近的乘数非常重要.即使两者分别工作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. 铲斗分类 - 精巧的铲斗,简单的加工,需要动态记忆,平均水平

因此,基数和桶分类是计数排序的两个有用的概括.他们在计算排序方面有很多共同之处,但在每种情况下我们都会失去一些东西并赢得一些东西.软件工程是在这些机会之间取得平衡.

Answer 2

基数排序与计数排序与桶排序.有什么不同？

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

在内存中排序比在磁盘上排序更快.但是,如果您有更多数据而不是内存,则需要另一个选项.您可以做的是一个桶排序,其中桶足够小以适应内存.即每个桶中有大量条目.这些你可以单独快速排序.

基数排序是特定类型的桶排序.它从顶部的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到max之间都需要使用存储桶）。

• 如果您使用的是bucketsort，则不知道要使用多少个存储桶。无论您使用什么哈希函数，都将确定存储桶的数量。

Answer 4

您的代码是计数排序的简单变体,没有数据,只有键.

基数排序是基于此方法的排序.计数排序的问题是内存要求: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排序的元素.

桶排序是计数排序的概括.您可以使用它从一些可预测的概率分布(例如,统一(0,1))中对实数进行排序.我们的想法是使用计数排序(使用floor(x*N_BUCKETS)密钥),然后只对每个桶进行独立排序.