桶排序是另外一种以O(n)或者接近O(n)的复杂度排序的算法. 它假设输入的待排序元素是等可能的落在等间隔的值区间内.一个长度为N的数组使用桶排序, 需要长度为N的辅助数组. 等间隔的区间称为桶, 每个桶内落在该区间的元素. 桶排序是基数排序的一种归纳结果
算法的主要思想: 待排序数组A[1…n]内的元素是随机分布在[0,1)区间内的的浮点数.辅助排序数组B[0….n-1]的每一个元素都连接一个链表.将A内每个元素乘以N(数组规模)取底,并以此为索引插入(插入排序)数组B的对应位置的连表中. 最后将所有的链表依次连接起来就是排序结果.
这个过程可以简单的分步如下:
1.设置一个定量的数组当作空桶子。
2. 寻访序列，并且把项目一个一个放到对应的桶子去。
3.对每个不是空的桶子进行排序。
4.从不是空的桶子里把项目再放回原来的序列中。
note: 待排序元素越均匀, 桶排序的效率越高. 均匀意味着每个桶在中间过程中容纳的元素个数都差不多,不会出现特别少或者特别多的情况, 这样在排序子程序进行桶内排序的过程中会达到最优效率.
note: 将元素通过恰当的映射关系将元素尽量等数量的分到各个桶(值区间)里面, 这个映射关系就是桶排序算法的关键.桶的标记(数组索引Index)的大小也要和值区间有对应关系。
基于数组的实现：
#include <stdio.h>
// Count数组大小
#define MAXNUM 100
// 功能：桶式排序
// 输入：待排序数组 arrayForSort[]
// 待排序数组大小 arraySize
// 待排序数组元素上界 maxItem；数组中的元素都落在[0, maxItem]区间
// 输出：void
void BucketSort(int arrayForSort[], int arraySize, int maxItem)
{
int Count[MAXNUM];
// 置空
for (int i = 0; i <= maxItem; ++i)
{
Count[i] = 0;
}
// 遍历待排序数组
for (int i = 0; i < arraySize; ++i)
{
++Count[arrayForSort[i]];
}
// 桶排序输出
// 也可以存储在数组中，然后返回数组
for (int i = 0; i <= maxItem; ++i)
{
for (int j = 1; j <= Count[i]; ++j)
{
printf("%3d", i);
}
}
printf("
");
}
void main()
{
// 测试
int a[] = {2, 5, 6, 12, 4, 8, 8, 6, 7, 8, 8, 10, 7, 6, 0, 1};
BucketSort(a, sizeof(a) / sizeof(a[0]), 12);
} 基于结构体的实现：
#ifndef BUCKETSORT_H
#define BUCKERSORT_H
#include <iostream>
template<typename T>
class BucketSort{
public:
void bucketSort( T *,int,int );
void printArr( T *,int );
};
/**
* 桶式排序法
*/
template<typename T> void BucketSort<T>::bucketSort( T *sortedArr,int arrLength,int max )
{
int *count=new int[max+1];
T *temp=new T[arrLength];
for( int i=0;i<max+1;++i )
count[i]=0;
/**
* 对相同的值计数
*/
for( int i=0;i<arrLength;++i )
{
++count[ sortedArr[i] ];
temp[i]=sortedArr[i];
}
/**
* 求出累加和
*/
for( int i=1;i<max+1;++i )
count[i]+=count[i-1];
/**
* 此处--count[ temp[i] ]不仅仅求出了temp[i]应该存放的位置，而且对象的计数值减了1,使得求出了temp[i]应该在的位置
* 此处从arrLength-1开始是为了稳定性
*/
for( int i=arrLength-1;i>=0;--i )
sortedArr[ --count[ temp[i] ] ]=temp[i];
delete [] count;
delete [] temp;
}
template<typename T> void BucketSort<T>::printArr( T *sortedArr,int arrLength )
{
for( int i=0;i<arrLength;++i )
{
std::cout<<sortedArr[i]<<" ";
}
}
#endif基于链表的实现1：
//头文件
#ifndef LIST_H
#define LIST_H
typedef int Item;
struct node
{
Item item;
struct node *next;
}; // 单链表节点
// 链表函数
int ListInit(struct node **list);
int ListAddItem(Item item,struct node *list);
int ListPopItem(Item *pitem,struct node *list);
void ListInsertSort(struct node *list);
// 桶排序
int bucket_sort(Item A[],Item B[],int length);
#endif//源文件
#include "list.h"
#include <stdlib.h>
#include <stdio.h>
// ==================================================
// 初始化,创建哨兵元素
// 注意,传入参数应该是链表头指针的地址，即指针的指针
// ==================================================
int ListInit(struct node **list)
{
struct node *pnew;
pnew = (struct node *)malloc(sizeof(struct node));
if(pnew == NULL)
return 0;
pnew->next = pnew;
*list = pnew;
return 1;
}
// ==================================================
// 向链表头部添加元素
// ==================================================
int ListAddItem(Item item,struct node *list)
{
struct node *pnew;
pnew = (struct node *)malloc(sizeof(struct node));
if(pnew == NULL)
return 0;
pnew->item = item;
pnew->next = list->next; // 添加到链表头部
list->next = pnew;
return 1;
}
// ==================================================
// 弹出链表第一个元素
// 若只有一个哨兵元素(即空链表),则返回0,但不删除哨兵元素
// 若链表中有元素,则弹出第一个元素的item，并将其所占内存收回
// ==================================================
int ListPopItem(Item *pitem,struct node *list)
{
struct node *pnew;
if(list->next == list) // 只有一个哨兵元素,返回0
return 0;
pnew = list->next;
*pitem = pnew->item;
list->next = list->next->next;
free(pnew);
return 1;
}
// ==================================================
// 对链表中的元素进行插入排序
// ==================================================
void ListInsertSort(struct node *list)
{
struct node *pscan1, *pscan2;
struct node *ptemp;
int change_status = 0; // 初始化,没有节点交换
pscan1 = list->next; // 外层循环,从第2个有效元素开始
while(pscan1->next != list) // 到链表头,则遍历结束
{
pscan2 = list;
change_status = 0;
while(pscan2 != pscan1)
{
if(pscan2->next->item > pscan1->next->item) // 大于,插入到psacn2和pscan2->next之前
{
ptemp = pscan1->next;
pscan1->next = ptemp->next; // 注意,此处改动了pscan1的next节点
ptemp->next = pscan2->next;
pscan2->next = ptemp;
change_status = 1;
break;
}
else
pscan2 = pscan2->next;
}
if(!change_status) // 未发生交换,则change_status下移
pscan1 = pscan1->next;
}
}
// ==================================================
// 桶排序
// A:要排序数组 B:存放结果数组,length:A元素个数
// ==================================================
int bucket_sort(Item A[],Item B[],int length)
{
static struct node *pbucket[10];
int i,j = 0;
// 桶初始化
for(i = 0; i < 10; i++)
ListInit(&(pbucket[i]));
// 将A分到各桶中
for(i = 0; i < length; i++)
{
if(!ListAddItem(A[i],pbucket[(A[i]/10)]))
break;
}
if(i != length)
return 0;
// 排序
for(i = 0; i < 10; i++)
ListInsertSort(pbucket[i]);
// 取出数据
for(i = 0; i < 10; i++)
{
while(ListPopItem(&B[j],pbucket[i]))
{
j++;
}
free(pbucket[i]);
}
return 1;
}
基于链表的实现2：
/*****************桶排序*****************************/
struct Node
{
int key_;
struct Node *next_;
Node(int key)
{
key_ = key;
next_ = NULL;
}
};
#define bucket_size 10 //与数组元素个数相等
void buck_sort(int arr[], int num)
{
Node *bucket_table[bucket_size];
memset(bucket_table, 0, sizeof(bucket_table));
//建立每一个头节点,头节点的key保存当前桶的数据量
for (int i = 0; i < bucket_size; i++)
bucket_table[i] = new Node(0);
int maxValue = arr[0];
for (int i = 1; i < num; i++)
{
if (arr[i] > maxValue)
maxValue = arr[i];
}
for (int j = 0; j < num; j++)
{
Node *ptr = new Node(arr[j]);//其余节点的key保存数据
//映射函数计算桶号
// index = (value * number_of_elements) / (maxvalue + 1)
int index = (arr[j] * bucket_size) / (maxValue + 1);
Node *head = bucket_table[index];
//该桶还没有数据
if (head->key_ == 0)
{
bucket_table[index]->next_ = ptr;
(bucket_table[index]->key_)++;
}
else
{
//找到合适的位置插入
while (head->next_ != NULL && head->next_->key_ <= ptr->key_)
head = head->next_;
ptr->next_ = head->next_;
head->next_ = ptr;
(bucket_table[index]->key_)++;
}
}
//将桶中的数据拷贝回原数组
int m, n;
for (m = 0, n = 0; n < num && m < bucket_size; m++, n++)
{
Node *ptr = bucket_table[m]->next_;
while (ptr != NULL)
{
arr[n] = ptr->key_;
ptr = ptr->next_;
n++;
}
n--;
}
//释放分配的动态空间
for (m = 0; m < bucket_size; m++)
{
Node *ptr = bucket_table[m];
Node *tmp = NULL;
while (ptr != NULL)
{
tmp = ptr->next_;
delete ptr;
ptr = tmp;
}
}
}
版权声明：本文为博主原创文章，未经博主允许不得转载。