桶排序

桶排序又称箱排序，其主要思想近乎分治法的思想。其原理是：讲待排序列（集合）中的元素分到数量有限的桶中，每个桶在进行排序。

桶排序不属于比较排序的一种，因此不受排序算法时间复杂度下限nlogn的限制。桶排序算法的时间复杂度为O(n)，但桶排序的空间复杂度也对应较高，是以空间换时间的排序算法。

同时，需要注意的是，桶排序对数据进行了一定的要求和限制，并不是所有情况下都能用桶排序：待排序列中的元素必须为整数。（根据《算法导论》的桶排序，其数据要求只能为自然数，但经过改进，负数也可以进行桶排序。）

桶排序的基本过程：
1、初始化桶，桶的个数不超过10个，一般将其编号为0-9号桶，对应待排序列中的元素最高位的数字；
2、遍历待排序列，根据最高位放入对应的桶中；
3、对于一个桶中的元素，再根据次高位分入子桶中，以此循环，直至分至个位数桶；
4、将桶按顺序进行遍历，得到排序元素。

伪代码

BUCKETSORT(A)
	n = A.length
	let B[0...n-1] be a new array
	for i = 0 to n-1
		b[i]=0
		//make B an empty list
	for i =1 to n
		insert A[i] into list B[(int)nA[i]]
	for i =0 to n-1
		sort list B[i] with insertion sort
	concatenate hte lists B[0...n-1] together in order

伪代码出自《算法导论》原书第3版，机械工业出版社，Thomas H.Cormen Charles E.Leiserson著
该伪代码与我的实际实现代码略有出入，但结果都是基本相同的。

例

若存在序列：{7, 50, 1, 4, 32, 7, 9, 5, 25, 6}，利用桶排序进行排序。
1、初始化桶0-5号，并将元素按十位放入对应桶中；

2、在0号桶内继续划分子桶，将元素按个位数对应放入子桶中；

3、按桶的顺序遍历输出元素，得到排序数组：1 4 5 6 7 7 9 25 32 50。

代码

（简化版代码，只能排两位数的情况）

#include <iostream>

#define N 10

using namespace std;

typedef struct Node{
	int value;
	Node *next = NULL;
};

void BucketSort(int a[], int length) {
	int *result = new int[length];
	int MIN = a[0];
	for (int i = 0; i < length; i++)
		if (a[i] < MIN)
			MIN = a[i];
	for (int i = 0; i < length; i++)	//处理负数的情况，使所有数都变为自然数
		a[i] -= MIN;

	Node* bucket[10];	//0-9号桶

	for (int i = 0; i < 10; i++)	
		bucket[i] = new Node();

	for (int i = 0; i < length; i++) {
		int bucketIndex = a[i] / 10;
		Node* node = new Node();
		node->value = a[i];
		Node* p = bucket[bucketIndex];	//通过十位找到对应的桶
		if (p->next == NULL)
			p->next = node;
		else {
			while (p->next != NULL && p->next->value <= node->value)	//插入排序
				p = p->next;
			node->next = p->next;
			p->next = node;
		}
	}

	int j = 0;
	for (int i = 0; i < 10; i++) {
		for (Node* p = bucket[i]->next; p != NULL; p = p->next)
			result[j++] = p->value;
	}

	for (int i = 0; i < length; i++)
		a[i] = result[i] + MIN;


	delete[] result;
}


int main() {
	int a[N] = { 7, 50, 1, 4, 32, 7, 9, 5, 25, 6 };
	int length = sizeof(a) / sizeof(a[0]);

	BucketSort(a, length);

	for (int i = 0; i < N; i++) 
		cout << a[i] << " ";
	cout << endl;

	system("pause");
	return 0;
}