释放双眼，带上耳机，听听看~！
大致思想：
桶排序的基本思想是假设数据在[min,max]之间均匀分布，其中min、max分别指数据中的最小值和最大值。那么将区间[min,max]等分成n份，这n个区间便称为n个桶。将数据加入对应的桶中，然后每个桶内单独排序。由于桶之间有大小关系，因此可以从大到小(或从小到大)将桶中元素放入到数组中。
分步骤图示说明：
设有数组 array = [63, 157, 189, 51, 101, 47, 141, 121, 157, 156, 194, 117, 98, 139, 67, 133, 181, 13, 28, 109]，对其进行桶排序
- 设置一个定量的数组当作空桶子。
- 寻访序列，并且把项目一个一个放到对应的桶子去。
- 对每个不是空的桶子进行排序。
- 从不是空的桶子里把项目再放回原来的序列中。
代码：
方式一
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
2
3#include <iostream>
4#include <vector>
5#include <algorithm>
6
7using namespace std;
8
9void bksort(float A[],int l,int h){
10 int size = h-l+1;
11 vector<float> b[size];//有size个数据，就分配size个桶
12 for(int i=l;i<=h;i++){
13 int bi = size*A[i];//元素A[i]的桶编号
14 b[bi].push_back(A[i]);//将元素A[i]压入桶中
15 }
16 for(int i=0;i<size;i++)
17 sort(b[i].begin(),b[i].end());//桶内排序
18 int idx = l;//指向数组A的下标
19 for(int i=0;i<size;i++){//遍历桶
20 for(int j=0;j<b[i].size();j++){//遍历桶内元素
21 A[idx++] = b[i][j];
22 }
23 }
24}
25
26int main(){
27 float A[] = {0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68};
28 bksort(A,2,9);
29 for(int i=0;i<10;i++)
30 cout<<A[i]<<" ";
31}
32
33
方式二：
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
2#include<iostream>
3#include<ctime>
4#include<vector>
5
6using namespace std;
7
8typedef unsigned long long MyLoop_t;
9
10template<typename Comparable>
11inline Comparable GetMax(vector<Comparable> &a) {
12 Comparable Max = 0;
13 for (MyLoop_t i = 0; i < a.size(); i++)
14 if (a[i] > a[Max])
15 Max = i;
16 return a[Max];
17}
18
19template<typename Comparable>
20void BuncketSort(vector<Comparable> &a) {
21 Comparable Max = GetMax(a);
22
23 MyLoop_t number = a.size();
24 MyLoop_t gap =(Max/a.size())+1;//算出每个桶容量
25 MyLoop_t buncketNumber = Max/gap+1;
26 struct node {
27 Comparable element;
28 node* next;
29 };
30 node **allBuncket = new node*[sizeof(node)*buncketNumber];//new出一个桶数组,emmmm我也成刘备了，不过我比他轻松，hhhh :-）
31 for (MyLoop_t i = 0; i < buncketNumber; i++)
32 {
33 allBuncket[i]=nullptr;
34 }
35 for (MyLoop_t i = 0; i < number; i++) {//数据入桶
36 MyLoop_t buncketLab = a[i]/gap;//取桶下标
37 if (allBuncket[buncketLab] == nullptr){//如果桶空
38 allBuncket[buncketLab] = new node;
39 allBuncket[buncketLab]->element = a[i];
40 allBuncket[buncketLab]->next = nullptr;
41 }
42 else {
43 if (allBuncket[buncketLab]->element > a[i]) {
44 node *temp = new node;
45 temp->element = a[i];
46 temp->next = allBuncket[buncketLab];
47 allBuncket[buncketLab] = temp;
48 }
49 else {
50 node* temp = allBuncket[buncketLab];
51 while (a[i] > temp->element && temp->next != nullptr && a[i]>temp->next->element) {
52 temp = temp->next;
53 }
54 node *newNode = new node;
55 newNode->element = a[i];
56 newNode->next = temp->next;
57 temp->next = newNode;
58 }
59 }
60 }
61 MyLoop_t j = 0;
62 for (MyLoop_t i = 0; i <buncketNumber; i++) {
63 if (allBuncket[i] != nullptr) {
64 a[j++] = allBuncket[i]->element;
65 node* temp = allBuncket[i]->next;
66 while(temp!=nullptr){
67 a[j++] = temp->element;
68 node * temp2 = temp->next;
69 delete temp;
70 temp = temp2;
71 }
72 delete allBuncket[i];
73 }
74 }
75 delete[] allBuncket;
76}
77
78int main()
79{
80 time_t start, end;
81 vector<int>a;
82 for (long long i = 0; i < 1000000; i++){
83 int c = rand();
84 a.push_back(c);
85 }
86 start = clock();
87 BuncketSort(a);
88 end = clock();
89 double totaltime = (double)(end - start) / CLOCKS_PER_SEC;
90 for (long long i = 1; i < 1000000; i++)
91 if (a[i] < a[i - 1]) {
92 cout << "error";
93 return 1;
94 }
95 cout << totaltime<<'s'<<endl;
96 system("pause");
97 return 0;
98}
99
100
101
算法复杂度：
