基本思想：桶排序将一个区间划分为N个相同大小的子区间，也就是桶。然后将输入数分别放到各个桶中。为了得到输出结果，先对每个桶中的数进行排序，然后遍历每个桶，按照次序把各个桶中的元素列出来即可。
----------
/*排序算法：桶排序
时 间：2018年1月16日
时间复杂度：O(n + k)
空间复杂度：O(n + k)
稳 定 性：稳定
by Ingran*/
----------
#include <iostream>
#include <time.h>
typedef struct Bucket_Node
{
int date;
struct Bucket_Node *Next;
}Node;
void Free_List(Node *head)
{
Node *N = head;
while (head != NULL)
{
N = head->Next;
delete head;
head = N;
}
}
void Bucket_Sort(int A[], int len)
{
Node *Bucket[10] = { 0 };//初始化十个空桶
Node *temp = NULL, *pre_temp = NULL;
for (int i = 0; i < len; i++)
{
int a = A[i] / 100;
if (Bucket[a] == 0)//把数据放入空桶中
{
Bucket[a] = new Node;
Bucket[a]->date = A[i];
Bucket[a]->Next = NULL;
}
else //对非空链表(非空桶)插入排序
{
pre_temp = temp = Bucket[a];
while (A[i] > temp->date)//比较数组中的元素与桶中元素的大小
{
pre_temp = temp;
temp = temp->Next;
if (temp == NULL)
break;
}
if (temp == NULL)//插入到最后的位置
{
temp = new Node;
temp->date = A[i];
temp->Next = NULL;
pre_temp->Next = temp;
}
else if (temp == Bucket[a])//插入到第一个位置
{
temp = new Node;
temp->date = A[i];
temp->Next = Bucket[a];
Bucket[a] = temp;
}
else //插入到中间
{
temp = new Node;
temp->date = A[i];
temp->Next = pre_temp->Next;
pre_temp->Next = temp;
}
}
}
Node *Input = NULL;
for (int i = 0; i < 10; i++)
{
Input = Bucket[i];
while (Input != NULL)
{
std::cout << Input->date<<" ";
Input = Input->Next;
}
Free_List(Bucket[i]);
}
}
int main()
{
int *a = nullptr;
int n = 0;
srand((unsigned)time(NULL));
std::cout << "请输入随机数的个数：" << std::endl;
std::cin >> n;
a = new int[n];
for (int i = 0; i < n; i++)
{
a[i] = rand() % 1001;
std::cout << a[i] << " ";
}
std::cout << std::endl;
Bucket_Sort(a, n);
system("pause");
return 0;
}