本文主要是介绍《啊哈！算法》简单桶排序（Simple Bucket Sort），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
《啊哈！算法》简单桶排序（Simple Bucket Sort）
首先想想如何简单地排序？
假设我们有5个学生，分数分别是5, 3, 5, 2, 8，满分10分。
由实际可知，分数范围在[0,10]，闭区间范围内。
首先申请一个一维数组int arr[11]， 是从[0, 10]。
这里认为第i个元素代表得i分的人的数目。
比如i=0，arr[0]=3，那么代表得0分的人有三个。
首先第一个人分数是5，那么就arr[5]=arr[5]+1；
第二个人分数是3，那么就arr[3]=arr[3]+1；
第三个人分数是5，那么就arr[5]=arr[5]+1；
第四个人分数是2，那么就arr[2]=arr[2]+1；
第五个人分数是8，那么就arr[8]=arr[8]+1；
然后再依次输出即可（或者置回对应的位置）。
a[2]为1表示2出现过一次，那么就输出一个2；
a[n]为m表示n出现过m次，那么就输出m个n；
C Code:
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>#define SAFE_FREE(p) {free(p);p=NULL;}/************************************************* 函数名称：print_array* 参数列表：1.int *parray:一个int类型指针，指向一个数组首地址* 2.int n：一个int类型变量，指明数组大小* 函数描述：输出数组中每个元素* 返回值 ：void* Author ：test1280* History ：2017/04/14* *********************************************/
void print_array(int *parray, int n)
{int i;for (i=0; i<n; i++){printf("%d ", parray[i]);}printf("\n");
}/*********************************************** 函数名称：bucketSort* 参数列表：* int *parr：待排序数组起始位置* int n：有多少个元素* int buckets：有多少个桶（即最大的位置）* 函数描述：简化版桶排序* Author ：test1280* History ：2017/04/18* **********************************************/
void bucketSort(int *parr, int n, int buckets)
{int *res = (int *)malloc(sizeof(int) * (buckets + 1));if (res == NULL){return ;}memset(res, 0, sizeof(int) * (buckets + 1));int i=0;while (i<n){res[parr[i]]++;i++;}int index = 0;for (i=0; i <= buckets; i++){while (res[i]--){parr[index++] = i;}}SAFE_FREE(res);
}int main()
{int arr[] = {8, 100, 50, 22, 15, 6, 1, 1000, 999, 0, 0, 50, 1};printf("before sort:\n");print_array(arr, 13);bucketSort(arr, 13, 1000);printf("after sort:\n");print_array(arr, 13);return 0;
}（注：我的代码和原书中有些不一样。）
输出结果：
[test1280@localhost sort]$ ./main
before sort:
8 100 50 22 15 6 1 1000 999 0 0 50 1
after sort:
0 0 1 1 6 8 15 22 50 50 100 999 1000这样排序的特点是，必须知道值得范围，然后做一下映射，记录在一个数组里面。
我个人认为，很有点Hash。
刚刚是从小到大进行排序，从大到小进行排序只需要修改一下遍历的顺序即可。
/*********************************************** 函数名称：bucketSort* 参数列表：* int *parr：待排序数组起始位置* int n：有多少个元素* int buckets：有多少个桶（即最大的位置）* 函数描述：简化版桶排序* Author ：test1280* History ：2017/04/18* **********************************************/
void bucketSort(int *parr, int n, int buckets)
{int *res = (int *)malloc(sizeof(int) * (buckets + 1));if (res == NULL){return ;}memset(res, 0, sizeof(int) * (buckets + 1));int i=0;while (i<n){res[parr[i]]++;i++;}int index = 0;for (i=buckets; i >=0; i--){while (res[i]--){parr[index++] = i;}}SAFE_FREE(res);
}
输出结果：
[test1280@localhost sort]$ ./main
before sort:
8 100 50 22 15 6 1 1000 999 0 0 50 1
after sort:
1000 999 100 50 50 22 15 8 6 1 1 0 0桶排序简单易懂，但是存在一些问题：
1.如果只有3个数需要排序，但是最大的和最小的相差20000，那么就有很多的空间被浪费；
2.如果是小数，或者别的比较难以映射成整数的情形下，比较难处理。
文中也提到，真正的桶排序要比这个复杂一些，后续我看到再进行记录整理。
注：此篇Blog为读《啊哈！算法》笔记。
这篇关于《啊哈！算法》简单桶排序（Simple Bucket Sort）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
