import java.util.ArrayList;

/**
 * @author yumu
 * @date 2022/8/25
 */
public class BucketSort {

    public void bucketSort(int[] nums) {
        int n = nums.length;
        int mn = nums[0], mx = nums[0];
        // 找出數(shù)組中的最大最小值
        for (int i = 1; i < n; i++) {
            mn = Math.min(mn, nums[i]);
            mx = Math.max(mx, nums[i]);
        }
        int size = (mx - mn) / n + 1; // 每個桶存儲數(shù)的范圍大小，使得數(shù)盡量均勻地分布在各個桶中，保證最少存儲一個
        int cnt = (mx - mn) / size + 1; // 桶的個數(shù)，保證桶的個數(shù)至少為1
        List<Integer>[] buckets = new List[cnt]; // 聲明cnt個桶
        for (int i = 0; i < cnt; i++) {
            buckets[i] = new ArrayList<>();
        }
        // 掃描一遍數(shù)組，將數(shù)放進桶里
        for (int i = 0; i < n; i++) {
            int idx = (nums[i] - mn) / size;
            buckets[idx].add(nums[i]);
        }
        // 對各個桶中的數(shù)進行排序，這里用庫函數(shù)快速排序
        for (int i = 0; i < cnt; i++) {
            buckets[i].sort(null); // 默認是按從小打到排序
        }
        // 依次將各個桶中的數(shù)據(jù)放入返回數(shù)組中
        int index = 0;
        for (int i = 0; i < cnt; i++) {
            for (int j = 0; j < buckets[i].size(); j++) {
                nums[index++] = buckets[i].get(j);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {19, 27, 35, 43, 31, 22, 54, 66, 78};
        BucketSort bucketSort = new BucketSort();
        bucketSort.bucketSort(nums);
        for (int num: nums) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

#include <iostream>
#include <vector>

using namespace std;

class BucketSort {
public:
    void bucketSort(vector<int> &nums) {
        int n = nums.size();
        int mn = nums[0], mx = nums[0];
        for (int i = 1; i < n; i++) {
            mn = min(mn, nums[i]);
            mx = max(mx, nums[i]);
        }
        int size = (mx - mn) / n + 1;   // size 至少要為1
        int cnt = (mx - mn) / size + 1; // 桶的個數(shù)至少要為1
        vector<vector<int>> buckets(cnt);
        for (int i = 0; i < n; i++) {
            int idx = (nums[i] - mn) / size;
            buckets[idx].push_back(nums[i]);
        }
        for (int i = 0; i < cnt; i++) {
            sort(buckets[i].begin(), buckets[i].end());
        }
        int index = 0;
        for (int i = 0; i < cnt; i++) {
            for (int j = 0; j < buckets[i].size(); j++) {
                nums[index++] = buckets[i][j];
            }
        }
    }
};


int main() {
    vector<int> nums = {19, 27, 35, 43, 31, 22, 54, 66, 78};
    BucketSort().bucketSort(nums);
    for (auto num: nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}