桶排序的思路基本就三步:
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] << " ";
}