本文实例讲述了C语言实现桶排序的方法。分享给大家供大家参考，具体如下：
一、定义
假定：输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…将n个输入元素分配到这些桶中，对桶中元素进行排序，然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组，指向桶（链表）。
二、性能
对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：
O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)
快排的时间复杂度为n*log2(n)
当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。
桶排序是稳定的
三、实现
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
/*==============================
8 name:bucket sort
--------------------------------
time complexity:
average
O(n+nlogn-nlogm)
--------------------------------
space complexity:
O(n)
--------------------------------
stability:
unstable
==============================*/
//suppose: 0<data[i]<100
//we should design the project function based on the data distribution
void bucket_sort(std::vector<int> &a)
{
std::vector<std::vector<int>> bucket;
bucket.resize(10);
std::vector<int>::iterator it=a.begin();
while(it!=a.end())
{
int idx=*it/10;
bucket[idx].push_back(*it);
it++;
}
std::vector<std::vector<int>>::iterator it1=bucket.begin();
while(it1!=bucket.end())
{
simple_sort(*it1);
it1++;
}
it=a.begin();
it1=bucket.begin();
while(it!=a.end() && it1!=bucket.end())
{
std::vector<int>::iterator tmp_it=(*it1).begin();
while(tmp_it!=(*it1).end())
{
*it=*tmp_it;
tmp_it++;
it++;
}
it1++;
}
}
|
希望本文所述对大家C语言程序设计有所帮助。
原文链接：http://blog.csdn.net/cjc211322/article/details/38176809