## 桶排序 1. 基本思想：桶排序是计数排序的升级版。它利用函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序的工作原理：假设输入数据服从均匀分布，将数据分到有限的桶里，每个桶再分别排序（有可能使用别的排序算法或以递归的排序方式继续使用桶排序的算法进行排序）。 ``` void bucketSort(vector<int>& data, int bucketSize) { int min = data[0]; int max = data[0]; for (auto x : data) { if (x < min) min = x; if (x > max) max = x; } int bucketCount = (max - min) / bucketSize + 1; vector<vector<int>> bucket(bucketCount); for (auto x : data) { bucket[(x - min) / bucketSize].push_back(x); } for (int i = 0; i < bucketCount; ++i) { std::sort(bucket[i].begin(), bucket[i].end()); } int index = 0; for (int i = 0; i < bucketCount; ++i) { for (auto x : bucket[i]) data[index++] = x; } } ```