C++基于STL库实现箱排序
箱排序简单介绍：
箱排序是一种分配排序方法。这是一种不需要比较的排序方法，可以让时间复杂度降为一线性阶O(n)。常用的分配排序有箱排序和基数排序。而基数排序是基于箱排序基础上实现的，所以这里着重介绍箱排序。
箱排序的基本思想是：设置若干个箱子，依次扫描待排序的记录R[0]、R[1]、R[2]……R[n-1]，把关键字等于K的记录全部装入第k个箱子里，然后依次将各非空的箱子首尾连接起来。
具体算法描述:
void BucketSort(float arr[], int n) {
vector<float>* bucket = new vector<float>[n];
for (int i = 0; i < n; i++) {
int key = arr[i] * n;
bucket[key].push_back(arr[i]);
}
for (int i = 0; i < n; i++) {
sort((bucket[i].begin()), (bucket[i].end()));
}
int index = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < bucket[i].size(); j++) {
arr[index++] = bucket[i][j];
}
}
};
上述代码中，使用了一个指向float类型的向量Vector来充当箱子。如果想要自己实现这个效果，可以使用一个指向float类型的指针数组。然后将待排序的数组按照值存入对应的箱中。
通过调用stl的sort函数，实现对每个箱子中的元素排序。
然后将所有箱子首尾相连。实现了排序的效果。时间复杂度为O(n)
但是箱排序只适合关键字取值范围较小的情况下，否则需要的箱子数目M太多，会导致存储空间的浪费和计算时间的增长。但若仔细分析关键字的结构。就可能得出对箱排序结果的改进。
改进后的排序方法就是基数排序。这里，基数排序就不在赘述。由于实现不是很难，所以我们在这里只给出箱排序的完整代码
#include <algorithm>是不可缺少的，std:sort的方法可能需要包含该头文件才可以使用。在有些版本的编译器上，若要使用sort函数是一定要包含这个头文件的（例如Vs2017）
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
void BucketSort(float arr[], int n) {
vector<float>* bucket = new vector<float>[n];
for (int i = 0; i < n; i++) {
int key = arr[i] * n;
bucket[key].push_back(arr[i]);
}
for (int i = 0; i < n; i++) {
sort((bucket[i].begin()), (bucket[i].end()));
}
int index = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < bucket[i].size(); j++) {
arr[index++] = bucket[i][j];
}
}
};
int main() {
float arr[10] = { 0.33,0.9,0.8,0.7,0.6,0.5,0.4,0.3,0.2,0.1 };
BucketSort(arr, 10);
for (int i = 0; i < 10; i++) {
cout << arr[i] << "\t";
}
return 0;
}
