首页 > 代码库 > 桶排序
桶排序
桶排序 (Bucket sort)将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。
桶排序最好情况下使用线性时间O(n)，很显然桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为 其它部分的时间复杂度都为O(n);很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
#include <iostream>
using namespace std;
int a[] = { 1, 255, 36, 32, 23, 16 };
const int len = sizeof(a) / sizeof(int);
int b[10][len + 1] = { 0 };
void bucketsort(int a[]);
void distributeelements(int a[], int b[10][len + 1], int digits);
void collectelements(int a[], int b[10][len + 1]);
int numofdigits(int a[]);
void zeroBucket(int b[10][len + 1]);
int main()
{
cout << "原始数组：";
for (int i = 0; i < len; i++)
{
cout << a[i]<<" ";
}
cout << endl;
bucketsort(a);
cout << "排序后数组：";
for (int i = 0; i < len; i++)
{
cout << a[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
void bucketsort(int a[])
{
int digits = numofdigits(a);
//cout << digits << endl;
for (int i = 1; i <= digits; i++)
{
distributeelements(a, b, i);
collectelements(a, b);
if (i != digits)
zeroBucket(b);
}
}
int numofdigits(int a[])
{
int largest = 0;
for (int i = 0; i < len; i++)
if (a[i]>largest)
largest = a[i];
int digits = 0;
while (largest)
{
digits++;
largest /= 10;
}
return digits;
}
void distributeelements(int a[], int b[10][len + 1], int digits)
{
int divisor = 10;
for (int i = 1; i < digits; i++)
divisor *= 10;
for (int j = 0; j < len; j++)
{
int numofdigits = (a[j] % divisor - a[j] % (divisor / 10)) / (divisor / 10);
int num = ++b[numofdigits][0];
b[numofdigits][num] = a[j];
}
}
void collectelements(int a[], int b[10][len + 1])
{
int k = 0;
for (int i = 0; i < 10; i++)
for (int j = 1; j <= b[i][0]; j++)
a[k++] = b[i][j];
}
void zeroBucket(int b[][len + 1])
{
for (int i = 0; i < 10;i++)
for (int j = 0; j < len + 1; j++)
b[i][j] = 0;
}
参考：百度百科（桶排序）
桶排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。