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

``````
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;

}

}

}

``````

``````
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 ]

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;

}

}

``````

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 内存)
• 桶排序--复杂，处理简单，需要动态内存，平均性能好