桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
在额外空间充足的情况下，尽量增大桶的数量 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
1. 什么时候最快
当输入的数据可以均匀的分配到每一个桶中。
2. 什么时候最慢
当输入的数据被分配到了同一个桶中。
3. 示意图
元素分布在桶中：
然后，元素在每个桶中排序：
代码实现 JavaScript 实例function bucketSort ( arr , bucketSize ) {
if ( arr. length === 0 ) {
return arr
}
var i
var minValue = arr [ 0 ]
var maxValue = arr [ 0 ]
for ( i = 1 i nodes_space) { printf("out of memory,File:%s, Func:%s, Line:%d ", __FILE__, __func__, __LINE__) goto exit_2 }return space_mgr exit_2: free(space_mgr) exit_1: return NULL } BucketManager* init_buckets(int bucket_nums) { BucketManager* bucket_mgr = (BucketManager*)malloc(sizeof(BucketManager)) if (!bucket_mgr) { printf("out of memory,File:%s, Func:%s, Line:%d ", __FILE__, __func__, __LINE__) goto exit_1 } bucket_mgr->nums = bucket_nums bucket_mgr->buckets = (Node**)calloc(bucket_mgr->nums, sizeof(Node*)) if (!bucket_mgr->buckets) { printf("out of memory,File:%s, Func:%s, Line:%d ", __FILE__, __func__, __LINE__) goto exit_2 } return bucket_mgr exit_2: free(bucket_mgr) exit_1: return NULL } Node* get_bucket_space(BucketSpaceManager* space_mgr) { if (space_mgr) { return &space_mgr->nodes_space[space_mgr->index++] } else { return NULL } } void release_bucket_space(BucketSpaceManager* space_mgr) { if (space_mgr) { if (space_mgr->nodes_space) { free(space_mgr->nodes_space) } free(space_mgr) } } void release_buckets(BucketManager* buckets_mgr) { if (buckets_mgr) { if (buckets_mgr->buckets) { free(buckets_mgr->buckets) } free(buckets_mgr) } }int find_max_min(int* arr, int size, int* p_max, int* p_min) { if (size *p_max) { *p_max = arr[i] } if (arr[i] *p_min) { *p_min = arr[i] } } return 0 } int insert_bucket(BucketManager* bucket_mgr, int index, Node* new_node) { Node* cur, *pre if (!bucket_mgr->buckets[index]) { bucket_mgr->buckets[index] = new_node } else { /** 桶内使用插入排序 */ cur = bucket_mgr->buckets[index] pre = cur while (cur->list_next &&new_node->elem >cur->elem) { pre = cur cur = cur->list_next }if (new_node->elem elem) { if (pre == cur) { new_node->list_next = cur bucket_mgr->buckets[index] = new_node } else { new_node->list_next = cur pre->list_next = new_node } } else { cur->list_next = new_node }} return 0 } void bucket_sort(int* arr, int size) { int max, min int ret = find_max_min(arr, size, &max, &min) if (ret <0) { return }BucketSpaceManager* space_mgr = init_bucket_space(size) if (!space_mgr) { printf("out of memory,File:%s, Func:%s, Line:%d ", __FILE__, __func__, __LINE__) goto exit_1 }int bucket_nums = (max - min) / BUCKET_SIZE + 1 BucketManager* bucket_mgr = init_buckets(bucket_nums) if (!bucket_mgr) { goto exit_2 } int i for (i = 0i size++i) { int index = (arr[i] - min) / BUCKET_SIZE Node* new_node = get_bucket_space(space_mgr) if (!new_node) { goto exit_3 } new_node->elem = arr[i] new_node->list_next = NULL insert_bucket(bucket_mgr, index, new_node) } for (i = 0i bucket_mgr->nums++i) { Node* node = bucket_mgr->buckets[i] while(node) { printf("%d ", node->elem) node = node->list_next } } printf(" ") exit_3: release_buckets(bucket_mgr) exit_2: release_bucket_space(space_mgr) exit_1: return }
下载测试代码
以上为桶排序算法详细介绍，插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点，用一张图概括：
关于时间复杂度
平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
名词解释：
n：数据规模
k："桶"的个数
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存
稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同
基数排序：
#include<math.h>testBS()
{
inta[] = {2, 343, 342, 1, 123, 43, 4343, 433, 687, 654, 3}
int *a_p = a
//计算数组长度
intsize = sizeof(a) / sizeof(int)
//基数排序
bucketSort3(a_p, size)
//打印排序后结果
inti
for(i = 0 i < size i++)
{
printf("%d\n", a[i])
}
intt
scanf("%d", t)
}
//基数排序
voidbucketSort3(int *p, intn)
{
//获取数组中的最大数
intmaxNum = findMaxNum(p, n)
//获取最大数的位数，次数也是再分配的次数。
intloopTimes = getLoopTimes(maxNum)
inti
//对每一位进行桶分配
for(i = 1 i <= loopTimes i++)
{
sort2(p, n, i)
}
}
//获取数字的位数
intgetLoopTimes(intnum)
{
intcount = 1
inttemp = num / 10
while(temp != 0)
{
count++
temp = temp / 10
}
returncount
}
//查询数组中的最大数
intfindMaxNum(int *p, intn)
{
inti
intmax = 0
for(i = 0 i < n i++)
{
if(*(p + i) > max)
{
max = *(p + i)
}
}
returnmax
}
//将数字分配到各自的桶中，然后按照桶的顺序输出排序结果
voidsort2(int *p, intn, intloop)
{
//建立一组桶此处的20是预设的根据实际数情况修改
intbuckets[10][20] = {}
//求桶的index的除数
//如798个位桶index=(798/1)%10=8
//十位桶index=(798/10)%10=9
//百位桶index=(798/100)%10=7
//tempNum为上式中的1、10、100
inttempNum = (int)pow(10, loop - 1)
inti, j
for(i = 0 i < n i++)
{
introw_index = (*(p + i) / tempNum) % 10
for(j = 0 j < 20 j++)
{
if(buckets[row_index][j] == NULL)
{
buckets[row_index][j] = *(p + i)
break
}
}
}
//将桶中的数，倒回到原有数组中
intk = 0
for(i = 0 i < 10 i++)
{
for(j = 0 j < 20 j++)
{
if(buckets[i][j] != NULL)
{
*(p + k) = buckets[i][j]
buckets[i][j] = NULL
k++
}
}
}
}
桶排序
#include <stdio.h>#define MAXNUM 100
void bucksort(int arr[], int N, int M)
{
int count[MAXNUM]
for (int i=0 i<=M i++)
{
count[i]=0
}
for (int i=0 i<N i++)
{
++count[arr[i]]
}
for (int i=0 i<=M i++)
{
for (int j=1 j<=count[i] j++)
{
printf("%d ",i)
}
}
}
int main()
{
int a[]={2,5,6,12,4,8,8,6,7,8,8,10,7,6}
bucksort(a,sizeof(a)/sizeof(a[0]),12)
return 0
}
运用桶排序即可，但有局限性只能应用于整数。自己去百度具体代码，看懂算法在自己写代码。
桶排序
(Bucket
sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是
比较排序，他不受到
O(n
log
n)
下限的影响。
1.N个数字（整形）
2.求出最大的数字的位数m
3.由于数字都是0到9组成，做10个桶，0到9，将N个数字依次放入桶里面
3.1
从个位数开始，从各位数字开始，将地i（i<m）为数字相同的数字，依次放入对应的桶中
3.2
从地0个桶开始，将所有桶中的数字取出，作为一个新的数字
3.2
重复上面两步，直至m为数字
4.最后排序的为从小到大的数组排序。
因为是数据排序，所以设置的桶的键值为0~9共十个桶。每次从数据的最后一个数位开始扫描，如果这个数位的值与桶的键值相等，就把这个数据放入桶内。桶可以看作是一个有序的链表，后进入的元素排在先进入的数据的后面，直到所有的数据都完成扫描，算作一次扫描。以后依次取倒数第二个扫描，按照桶的键值开始扫描，同样把数位的值与桶的键值相等的数据放入桶内。直到所有数据的最高数位也完成扫描。最后一次扫描完成，桶的键值从低到高，把这些链表串起来输出的结果就是原来数据的从小到大排序。
---------------------------------------------------------------------------------------------------
代码（来自《数据结构算法Visual.C.6.0程序集》）
void
main()
{cout<<"bucketsort.cpp运行结果:\n"
int
array[SIZE]
cout<<"原数组:\n"
srand(time(0))
for(int
i=0i<SIZE++i)
{array[i]=rand()0
cout<<setw(3)<<array[i]}
cout<<'\n'
cout<<"排序过程演示:\n"
bucketSort(array)
cout<<"排序后数组:\n"
for(int
j=0j<SIZE++j)
cout<<setw(3)<<array[j]
cout<<endlcin.get()
}
//
桶排序算法
void
bucketSort(int
a[])
{int
totalDigits,bucket[10][SIZE]={0}
totalDigits=numberOfDigits(a,SIZE)
for(int
i=1i<=totalDigits++i)
{
distributeElements(a,bucket,i)
collectElements(a,bucket)
//将桶数组初始化为0
if(i!=totalDigits)
zeroBucket(bucket)
for(int
j=0j<SIZE++j)
cout<<setw(3)<<a[j]
cout<<endl}
}
//确定单下标数组的最大数的位数
int
numberOfDigits(int
b[],int
arraySize)
{
int
largest=b[0],digits=0
for(int
i=1i<arraySize++i)
if(b[i]>largest)
largest=b[i]
while(largest!=0)
{
++digits
largest/=10}
return
digits
}
//
将单下标数组的每个值放到桶数组的行中
void
distributeElements(int
a[],int
buckets[][SIZE],int
digit)
{int
divisor=10,bucketNumber,elementNumber
for(int
i=1i<digit++i)
divisor*=10
for(int
k=0k<SIZE++k)
{
bucketNumber=(a[k]%divisor-a[k]%(divisor/10))/(divisor/10)//求取地m为数字
elementNumber=++buckets[bucketNumber][0]//buckets[bucketNumber][0]
表示桶中的数字个数
buckets[bucketNumber][elementNumber]=a[k]//放入对应的桶中
}
}
//将桶数组的值复制回原数组
void
collectElements(int
a[],int
buckets[][SIZE])
{int
subscript=0
for(int
i=0i<10++i)
for(int
j=1j<=buckets[i][0]++j)
a[subscript++]=buckets[i][j]
}
//将桶数组初始化为0
void
zeroBucket(int
buckets[][SIZE])
{for(int
i=0i<10++i)
for(int
j=0j<SIZE++j)
buckets[i][j]=0}
