桶排序

BucketSort(A, mx, n) {
    // mx 为最大数值，n 为桶数量
    // 定义 n 个桶
    define bucket[n]
    // 计算分块的块大小
    bucketsize = mx/n + 1
    // 根据元素的排序关键字数值分块
    for i = 1 to A.length
        bucket[A[i]/bucketsize].PushBack(A[i])
    for i = 0 to n-1
        InsertSort(bucket[i])
    cnt = 0
    for i = 0 to n-1
        for j = 1 to bucket[i].length
            A[++cnt] = bucket[i][j]
}

#include <bits/stdc++.h>
using namespace std;

#ifndef _BUCKET_
#define _BUCKET_
#define ll int
#define MAXN 100005
#define MAXBUK 1000
#define INF 10000000

// 桶排序
template < typename T >
struct Bucket {
    vector < pair<T, ll> > bucket[MAXN];
    Bucket() {}
    // 插入排序
    void insertSort(vector < pair<T, ll> > & bkt) {
        for(ll i = 1; i < bkt.size(); ++i) {
            pair <T, ll> key = bkt[i];
            ll j = i - 1;
            while(~j && bkt[j].second > key.second) {
                bkt[j+1] = bkt[j];
                j--;
            }
            bkt[j+1] = key;
        }
    }
    // 桶排序
    void bucketSort(T *bA, T *eA, ll *bK, ll *eK, ll mx = INF, ll bn = MAXBUK) {
        ll len_A = eA - bA;
        ll len_K = eK - bK;
        T *A = bA;
        ll *K = bK;
        ll bucketsize = mx/bn + 1;
        // 判断关键字数组大小与元素数组大小是否吻合
        assert(len_A == len_K);
        // 初始化桶
        for(ll i = 0; i < bn; ++i) {
            bucket[i].clear();
        }
        // 将元素放入桶中
        for(ll i = 0; i < len_K; ++i) {
            bucket[K[i]/bucketsize].push_back(pair<T, ll>{A[i], K[i]});
        }
        // 对每一个桶进行插入排序
        ll cnt = 0;
        for(ll i = 0; i < bn; ++i) {
            insertSort(bucket[i]);
            for(ll j = 0; j < bucket[i].size(); ++j) {
                A[cnt++] = bucket[i][j].first;
            }
        }

    }
};
#endif