桶排序的思路基本就三步：
1.按照数组的上下界与长度将其划分为若干个区间，对应若干个桶，将元素放入对应范围的桶里
2.对每一个桶内部排序
3.遍历所有桶，依次将桶中元素输出
时间和空间开销都是O(n+k),n是数组长度，k是桶的个数。
划分区间采取归一化策略；
桶用二维数组动态分配内存；
桶的内部排序采取快排，时间复杂度O(NlogN)。
#include<iostream> using namespace std; void quick_sort(int a[], int l, int r) { if (l < r) { int i = l, j = r, x = a[i]; while (i < j) { while (i<j && a[j]>x) j--; if (i < j) a[i++] = a[j]; while (i < j && a[i] < x) i++; if (i < j) a[j--] = a[i]; } a[i] = x; quick_sort(a, l, i-1); quick_sort(a, i + 1, r); } } void bksort(int a[],int n) {//数组长度 int min = a[0], max = a[0]; for (int i = 0; i < n; i++) { if (a[i] < min) min = a[i]; if (a[i] > max) max = a[i]; } int bkNum = (max - min) / n + 1, tmp = 0; int** bk = new int* [bkNum];//动态分配桶内存 for (int i = 0; i < bkNum; i++) bk[i] = new int[bkNum] {0}; int* k = new int[bkNum] {0};//动态分配k数组（存储每个桶元素个数） for (int i = 0; i < n; i++) { int index = (a[i]-min) / n;//定义元素存放的桶号 bk[index][k[index]++] = a[i]; } for (int i = 0; i < bkNum; i++) { quick_sort(bk[i], 0, k[i] - 1); cout << i << "号桶元素个数：" << k[i] << endl; for (int j = 0; j < k[i]; j++) { a[tmp++] = bk[i][j];//遍历桶中元素，依次存入原数组 } } } int main() { int a[] = { 1, 45, 32, 23, 22, 31, 47, 24, 4, 15, 55, 67, 59, 68, 89, 84 }; int len = sizeof(a) / sizeof(int); bksort(a, len); for (int i = 0; i < len; i++) cout << a[i] << " "; }