常用算法-桶排序

桶排序：

时间复杂度：O(N+N(log2N-log2M)),N个待排序，M个桶，M=N O(N)
空间复杂度：O(N+M)
原理：
将待排序的序列按照规则分组，每一组采用快速排序、插入排序的方式进行排序，然后按照次序将所有元素合并，得到一个有序的序列。关键在于构造基准值，放入对应的桶中
核心代码：
void bucketSort()
{
int size = count;
int bucketSize = 1;
while(size)
{
size /= 100;
bucketSize *= 10;
}
//构造桶的个数
bucketSize /= 10;
//最大值与最小值分组之间的数值
//取出列中最大值最小值
int max = list[0];
int min = list[0];
for (int i = 1;i < count;i++) {
max = qMax(max,list[i]);
min = qMin(min,list[i]);
}
int base = (max - min)/bucketSize + 1;
//元素放入对应桶中
QVector bucket[bucketSize];
for (int n = 0;n < count;n++) {
int index = (list[n] - min)/base;
bucket[index].push_back(list[n]);
}
//对桶内数据进行快速排序或者插入排序
for (int k = 0;k < bucketSize;k++) {
if(bucket[k].size() > 1)
{
quickSort(bucket[k],0,bucket[k].size()-1);
}
}
//有序取数据
int m = 0;
for (int q = 0;q < bucketSize;q++)
for (int p = 0;p < bucket[q].size();p++)
list[m++] = bucket[q][p];