桶排序算法是“分治法”的典型应用，主要思路是先“分桶”(或建捅)再“合桶”。其中最关键的是“分桶”，这一步最佳的时将整个待排序数组均匀分布在每个“分桶”内，然后再对每个“分桶”内部进行排序，最后将所有排序好的“分桶”依次遍历输出即可。这个思路感觉跟“计数排序算法”和“基数排序算法”十分相识。“计数排序”是通过下标将待排序数映射到“一个桶”内，然后再逐个取出；而“基数排序”是遍历所有“基数”，然后对每个基数进行一轮“计数排序”，最后完成整个数组排序。“桶排序”的“分桶”过程也是需要将待排序元素映射到“桶”内部，故桶分组采用数组，但是“桶”内部一串元素采用链表，目的是为了节省开销，提高效率。

平均时间复杂度为 O(n + m)，空间复杂度为 O(n * k)，最佳时间复杂度为O(n + m)。

桶排序主要应用在数组均匀分布或者呈现数列分布的情况最适合采用该排序。

一、代码实现分析

下面举一个具体例子。

1.1采用均匀分布方法“分桶”

a1 确定“分桶”个数

假如要对数组arr={ 2,0,1,6,8,10,5,99,87,333,2,0,1 }排序，假设需要桶的个数为bucketNum=std::ceil(size/3)，向上取整，反之桶个数不够映射时跑死越界。

if (nums.size() <= 1)
return;
auto minmax = std::minmax_element(nums.begin(), nums.end()); // a1 确定“分桶”个数
int min = *minmax.first;
int max = *minmax.second;
int bucketNum = std::ceil(nums.size() * 1.0 / 3); // 假设桶个数有这么多个，实际最优取值需要根据具体数组给定
vector<list<int>> bucket(bucketNum);

a2  确定桶间距gap

先找出最值，然后得出每个桶间距，即gap=(max-min)/bucketNum；此处考虑异常，假如gap==0则直接返回；

int gap = std::ceil((max - min) * 1.0 / bucketNum); // 每个桶间距，假设均匀分布
if (gap == 0) // 如果最大值等于最小值所以都是一样的元素不需要排序
return;
int index = 0;

a3  将待排序数组元素尽可能均匀依次映射入每个“分桶”

for (const auto& it : nums) // a2  将待排序数组元素尽可能均匀依次映射入每个“分桶”
{
    int index = (it - min) / gap; // 确定待排序数落在哪个分桶内，间隔长度/间距，取整后截断后面小数，左边闭区间
    bucket[index].push_back(it);
}

a4  对每个分桶依次进行排序

for (auto& it : bucket) // a3  对每个分桶依次进行排序
    it.sort();

a5  “合桶”，遍历每个“分桶”并依次输出“分桶”排序后的元素

for (const auto& it : bucket) // a4  “合桶”，遍历每个“分桶”并依次输出“分桶”排序后的元素
{
    for (const auto& iter : it)
    {
        nums[index] = iter;
        ++index;
    }
}

1.2完整代码

Sorts.h

#pragma once

#include <iostream>
#include <vector>

using namespace std;

struct Sorts {    
    void bucket(vector<int>& nums);    
    void print(vector<int>& nums);
};

Sorts.cpp

#include "Sorts.h"
#include <list>
#include <algorithm>

void Sorts::bucket(vector<int>& nums)
{    
    if (nums.size() <= 1)
        return;
    auto minmax = std::minmax_element(nums.begin(), nums.end()); // a1 确定“分桶”个数
    int min = *minmax.first;
    int max = *minmax.second;
    int bucketNum = std::ceil(nums.size() * 1.0 / 3); // 假设桶个数有这么多个，实际最优取值需要根据具体数组给定
    vector<list<int>> bucket(bucketNum);
    int gap = std::ceil((max - min) * 1.0 / bucketNum); // 每个桶间距，假设均匀分布
    if (gap == 0) // 如果最大值等于最小值所以都是一样的元素不需要排序
        return;
    int index = 0;
    
    for (const auto& it : nums) // a2  将待排序数组元素尽可能均匀依次映射入每个“分桶”
    {
        int index = (it - min) / gap; // 确定待排序数落在哪个分桶内，间隔长度/间距，取整后截断后面小数，左边闭区间
        bucket[index].push_back(it);
    }    
    for (auto& it : bucket) // a3  对每个分桶依次进行排序
        it.sort();
    for (const auto& it : bucket) // a4  “合桶”，遍历每个“分桶”并依次输出“分桶”排序后的元素
    {
        for (const auto& iter : it)
        {
            nums[index] = iter;
            ++index;
        }
    }
}

void Sorts::print(vector<int>& nums)
{
    for (const auto& it : nums)
        cout << it << ",";
    cout << endl;
}

main.cpp

 #include <vector>
#include "Sorts.h"

using namespace std;

int main()
{
    vector<int> nums = { 2,0,1,6,8,10,5,99,87,333,2,0,1 };
    Sorts sorts;
    sorts.print(nums);
    sorts.bucket(nums);
    sorts.print(nums);
   
	return 1;
}

1.3输出结果