题解 | #牛牛的桶排序#

c++题解：
桶排序就是将数据分入多个桶中，桶内单独排序，再依次输出。
1.设置一个定量的数组当作空桶子。
2.寻访序列，并且把项目一个一个放到对应的桶子去。
3.对每个不是空的桶子进行排序。
4.从不是空的桶子里把项目再放回原来的序列中。

  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型vector
     */
    vector<int> bucketSort(vector<int>& nums) {
        // write code here
        // 计入输入的最大值
        int maxValue = nums[0];
        for (int i = 1; i < nums.size(); i++)
            if (nums[i] > maxValue)  // 输入数据的最大值
                maxValue = nums[i];
        // 全是零的数组
        if(maxValue == 0){
            return nums;
        }
        // 设置10个桶，依次0，1，，，9
        const int bucketCnt = 10;
        vector<int> buckets[bucketCnt];
        // 桶的大小bucketSize根据数组最大值确定：比如最大值99， 桶大小10
        // 最大值999，桶大小100
        // 根据最高位数字映射到相应的桶，映射函数为 arr[i]/bucketSize
        int bucketSize = 1;
        while (maxValue) {      //求最大尺寸
            maxValue /= 10;
            bucketSize *= 10;
        }
        bucketSize /= 10;       //桶的个数
        // 入桶
        for (int i = 0; i < nums.size(); i++) {
            int idx = nums[i] / bucketSize;           //放入对应的桶
            buckets[idx].push_back(nums[i]);
            // 对该桶使用插入排序(因为数据过少，插入排序即可)，维持该桶的有序性
            for (int j = int(buckets[idx].size()) - 1; j > 0; j--) {
                if (buckets[idx][j] < buckets[idx][j - 1]) {
                    swap(buckets[idx][j], buckets[idx][j - 1]);
                }
            }
        }
        // 顺序访问桶，得到有序数组
        for (int i = 0, k = 0; i < bucketCnt; i++) {
            for (int j = 0; j < int(buckets[i].size()); j++) {
                nums[k++] = buckets[i][j];
            }
        }
        return nums;
    }
};