桶排序的单链表实现及其变种
《算法导论》中桶排序问题的单链表实现
《算法导论》CLRS 第八章 线性时间排序 8.4 桶排序 桶排序的思想就是把区间[0, 1)划分成n个相同大小的子区间，每一个区间称为桶（bucket）。然后，将n个输入数据分布到各个桶中去。因为输入数均匀且独立均匀分布在[0, 1)上，所以一般不会有很多数落在一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各个桶中的元素列出来即可。 在桶排序算法中，假设输入的是一个含n个元素的数组A，且每个元素满足0≤A[i]<1。另外，还需要一个辅助数组B[0..n-1]来存放链表（桶），并假设可以用某种机制来维护这些表。 BUCKET-SORT(A)
1 n ← length[A]
2 for i ← 1 to n
3 do insert A[i] into list B[⌊n A[i]⌋]
4 for i ← 0 to n - 1
5 do sort list B[i] with insertion sort
6 concatenate the lists B[0], B[1], . . ., B[n - 1] together in order下图表示出了桶排序作用于有10个数的输入数组上的操作过程。
AC代码：
// 待排序数组arr[1...n]内的元素是随机分布在[0,1)区间内的的浮点数
#include<iostream>
#define bucket_num 10 // 分配到多少个桶中，可设置
using namespace std;
struct ListNode
{
double value;
ListNode *next;
};
//桶排序主程序
void bucketSort(double* arr, int length)
{
ListNode key[bucket_num]; // 映射关系: int key <- ElemNum/bucket_num
int number = 0;
ListNode *p, *q; //插入节点临时变量
int counter = 0;
for(int i = 0; i < bucket_num; i++)
{
key[i].value = 0;
key[i].next = NULL;
}
for(int i = 0; i < length; i++)
{
ListNode *insert = new ListNode();
insert->value = arr[i];
insert->next = NULL;
number = arr[i] * bucket_num;
if(key[number].next == NULL)
{
key[number].next = insert;
}
else
{
p = &key[number];
q = key[number].next;
while((q != NULL) && (q->value <= arr[i]))
{
q = q->next;
p = p->next;
}
insert->next = q;
p->next = insert;
}
}
for(int i = 0; i < bucket_num; i++)
{
p = key[i].next;
if(p == NULL)
continue;
while(p != NULL)
{
arr[counter++] = p->value;
p = p->next;
}
}
}
int main()
{
double arr[] = {0.78, 0.17, 0.39, 0.26, 0.72, 0.34, 0.94, 0.21, 0.12, 0.23};
int len=sizeof(arr)/sizeof(arr[0]);
bucketSort(arr, len);
for(int i = 0; i < len; i++)
{
cout << arr[i] << " ";
}
cout << endl;
return 0;
}参考：
http://www.cnblogs.com/juventus/archive/2012/06/06/2538834.html
相关链接：
http://www.programset.com/blog/blog/23 (感觉代码不太像 桶排序)
#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
void bucketsort(double* a, int n) {
list<double>* b = new list<double>[n];
for (int i = 0; i < n; i++) {
b[int(a[i])].push_back(a[i]);
}
for (int i = 0; i < n; i++) {
b[i].sort();
}
for (int i = 0,j=0; i < n; i++) {
while (b[j].size() < 1)j++;
a[i] = b[j].front();
b[j].pop_front();
}
}
int main() {
double arr[] = {0.1,1.1,2.2,3.5,1.5,2.3,7.5,1.7};
int n = 8;
bucketsort(arr, n);
for (int i = 0; i < 8; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}将2.3改为9.3时，程序会异常而终止...
1 n ← length[A]
2 for i ← 1 to n
3 do insert A[i] into list B[⌊n A[i]⌋]
4 for i ← 0 to n - 1
5 do sort list B[i] with insertion sort
6 concatenate the lists B[0], B[1], . . ., B[n - 1] together in order本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016年05月01日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读