桶排序

[GH1995]

    void bucket_sort(vector<int> &nums) {
        int n = nums.size();

        // 1) Create n empty buckets
        vector<vector<int>> buckets(n);

        // 2) Put elements in different buckets
        for (int i = 0; i < n; ++i)
            buckets[nums[i] / n].push_back(nums[i]);

        // 3) Sort individual buckets
        for (int i = 0; i < n; ++i)
            sort(buckets[i].begin(), buckets[i].end());

        // 4) Concatenate all buckets
        int index = 0;
        for (int i = 0; i < n; ++i)
            for (int j : buckets[i])
                nums[index++] = j;
    }