桶排序

将数组分到有限数量的桶子里，每个桶子再个别排序，有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序
时间复杂度：
最好：对于n个待排数据，m个桶，当n=m时，极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(n)
最坏：当m=1时，即极限情况下只有一个桶时。桶排序的最坏效率达到O(n * log n)
平均：n + n + n/m * log(n/m ) * m + n = 3n + n(log n - log m) = O(n + n(log n - log m))
空间复杂度：O(m + n)

void bucketSort(double array[], int size) {
    // 求数组最大值和最小值，并算出差值d
    double max = array[0];
    double min = array[0];
    for (int i = 1; i < size; i++) {
        if (array[i] > max) {
            max = array[i];
        }
        if (array[i] < min) {
            min = array[i];
        }
    }
    double d = max - min;
    // 一般创建的桶数量等于原始数列的元素数量，除了最后一个桶只包含数列最大值，前面各个桶的区间按照比例确定
    // OR 桶数量等于原始数列的元素数量+1，除了第一个桶只包含数列最小值，最后一个桶只包含数列最大值，中间各个桶的区间按照比例确定
    int bucketNum = size;
    vector<list<double>> bucketArr(bucketNum);
    // 遍历数组，将每个元素放入桶中
    for (int i = 0; i < size; i++) {
        int num = (int)((array[i] - min) * (bucketNum - 1) / d);
        bucketArr[num].push_back(array[i]);
    }
    // 对每个桶内部进行排序
    for (int i = 0; i < bucketArr.size(); i++) {
        bucketArr[i].sort();
    }
    // 放入数组
    int i = 0;
    for (auto& bucket : bucketArr) {
        for (auto& d : bucket) {
            array[i++] = d;
        }
    }
}