哦，这是桶排序
要了解桶排序之前，可以先看看上面小灰的那篇文章，我觉得是比较不错的。
桶排序也可以理解为分类排序，把不同的数据归类，归类之后再重新排序，每个桶里面的内容就是一类数据，然后对每个桶里面的数据进行排序。
至于需要多少个桶，我们可以根据每个桶能装的数据数量来反推计算。
比如我们有一千个数据 1000。
我们每个桶的数据区间是 200。
那我们就需要 1000/200 = 5个桶来装这些数据。
0 ~200
200 ~400
400 ~600
600 ~800
800 ~1000
我们看维基百科官方的图片解析
排序之前
排序之后
上代码
#include "stdio.h"
#include "string.h"
#define BUCKET_NUM 5 /*桶排序中桶的个数*/
#define BUCKET_STEP 200 /*假设需要排序的最大数值是 1000/5，10个桶，每个桶的范围是 1000/10 = 100*/
int bucket_sort(int *arr,int n)
{
int i,j,k,m;
int buck[BUCKET_NUM][n];
memset(buck,0,sizeof(buck));
/*数据放到对应的桶里面*/
for(i=0;i {
if(arr[i]<=BUCKET_STEP){
for(j=0;j if(buck[0][j] == 0){
buck[0][j] = arr[i];
break;
}
}
}else if(arr[i] > BUCKET_STEP && arr[i] <= 2*BUCKET_STEP){
for(j=0;j if(buck[1][j] == 0){
buck[1][j] = arr[i];
break;
}
}
}else if(arr[i] > 2*BUCKET_STEP && arr[i] <= 3*BUCKET_STEP){
for(j=0;j if(buck[2][j] == 0){
buck[2][j] = arr[i];
break;
}
}
}else if(arr[i] > 3*BUCKET_STEP && arr[i] <= 4*BUCKET_STEP){
for(j=0;j if(buck[3][j] == 0){
buck[3][j] = arr[i];
break;
}
}
}else if(arr[i] > 4*BUCKET_STEP && arr[i] <= 5*BUCKET_STEP){
for(j=0;j if(buck[4][j] == 0){
buck[4][j] = arr[i];
break;
}
}
}else{printf("error arr[%d]=%d \n",i,arr[i]);}
}
/*调试打印*/
for(i=0;i for(j=0;j if(buck[i][j]!= 0) printf("%d ",buck[i][j]);printf("\n");
/*对桶里面的数据进行排序*/
for(i=0;i for(j=0;j for(k=0;k if( buck[i][k] > buck[i][k+1]) {/*交换*/
buck[i][k] ^= buck[i][k+1];
buck[i][k+1] ^= buck[i][k];
buck[i][k] ^= buck[i][k+1];
}
}
}
}
/*打印*/
for(i=0;i for(j=0;j if(buck[i][j]!= 0) printf("%d ",buck[i][j]);printf("\n");
}
int main()
{
int i;
int arr[20] = {12,12,1,78,500,5,7,699,752,233,1,13,399,599,500,462,801,699,19,345};
for(i=0;i printf("%d ",arr[i]);printf("\n");
bucket_sort(arr,sizeof(arr)/sizeof(arr[0]));
return 0;
}
这个代码的思路我大概说一下，桶的数量和区间我先确定好了，然后呢，我把数据放到对应的桶里面去。
再然后呢，我使用冒泡排序把每个小桶里面的数据排序了一次。
原理上很简单。
如果我们把桶的数量确定为1，然后一个桶把所有的数据都存下来，这就是计数排序了，除了冒泡排序之外，我觉得计数排序是一种很容易记住的排序算法。桶排序其实有点啰嗦，原理不错，但是如果处理一些小数据的话，作用很小。
程序输出
weiqifa@bsp-ubuntu1804:~/c$ gcc tongpaixu.c && ./a.out
12 12 1 78 500 5 7 699 752 233 1 13 399 599 500 462 801 699 19 345
12 12 1 78 5 7 1 13 19 233 399 345 500 599 500 462 699 752 699 801
1 1 5 7 12 12 13 19 78 233 345 399 462 500 500 599 699 699 752 801
weiqifa@bsp-ubuntu1804:~/c$
评论