algorithm - 算法基数排序 vs 计数 vs 桶排序 有什么区别?

  显示原文与译文双语对照的内容
53 5

我正在读取基数。计数和桶排序的定义,它们似乎只是下面的代码:


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,则显示代码。

时间: 原作者:

128 0

让我们从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 ( ),在这里排序 array的10个元素,我们使用的是 670元素的array,主要为0. ! 要处理这个计数排序问题,我们有两种可能的归纳方法:

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;


 }


}



我们正在为内存增加附近的乘数。 利润也许,但在某些情况下,multiplier的乘数是非常重要的。 程序,工作一天和工作一周与用户视图不同,即使两个工作 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;


 }


 }


 }


 }



/* 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;


}



我们这里有什么? 我们正在交易一些复杂的桶结构和动态分配内存的需求,以及 static 内存的乘法器。

现在让我们回忆一下代码中所看到的内容:

  • 计算排序--简单桶,简单处理,内存开销
  • 基数排序--简单,复杂处理,速度开销( 而且还需要额外的static 内存)
  • 桶排序--复杂,处理简单,需要动态内存,平均性能好

基数和桶排序是计数排序的两个有用的归纳。 他们有很多与计数排序相同的事情,但是在每一个情况下,我们都失去了某些东西。 软件工程是关于这些机会之间的平衡。

101 1

基数排序 vs 计数 vs 桶排序。 有何区别?

桶排序将键或者元素排序为桶。 这些位置是任意的,可以是组合键的一部分,也可以是任何你喜欢的分布。 单个桶可能需要进一步排序。

在内存中排序比在磁盘上排序快。 但是,如果你的数据比内存中的数据多,你需要。 你可以做的是桶排序,其中桶是足够小,适合内存。 换句话说,每个bucket中有大量的条目。 这些你可以快速排序。

基数排序是一种特殊的桶排序类型。 它从顶部n 位或者n 位数开始,并可以使用一个基类排序,直到每个条目排序。

计数排序就像使用基数排序,除了使用整数值。 它对每个对象都有一个 bucket,而不是记录每个对象,它只计算出现的次数。 当你有一些可能的键并且你有许多重复的时候,这工作。

原作者:
...