桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定

思路：

根据数据规模，初始化合理桶数
将数列中的数据按照桶的规模进行映射，尽量保证数据被均匀的分布到桶中
每个桶使用插入排序排好子序列
最后使用双指针思想使用插入排序合并每个桶，完成排序

代码实现：

#include<iostream>

#include<vector>

using namespace std;

const int BUCKET_NUM = 10;

struct ListNode {

	explicit ListNode(int i = 0) :mData(i), mNext(NULL) {}

	ListNode* mNext;

	int mData;

};

ListNode* insert(ListNode* head, int val) {

	ListNode dummyNode;

	ListNode *newNode = new ListNode(val);

	ListNode *pre, *curr;

	dummyNode.mNext = head;

	pre = &dummyNode;

	curr = head;

	while (NULL != curr && curr->mData <= val) {

		pre = curr;

		curr = curr->mNext;

	}

	newNode->mNext = curr;

	pre->mNext = newNode;

	return dummyNode.mNext;

}

ListNode* Merge(ListNode *head1, ListNode *head2) {

	ListNode dummyNode;

	ListNode *dummy = &dummyNode;

	while (NULL != head1 && NULL != head2) {

		if (head1->mData <= head2->mData) {

			dummy->mNext = head1;

			head1 = head1->mNext;

		}

		else {

			dummy->mNext = head2;

			head2 = head2->mNext;

		}

		dummy = dummy->mNext;

	}

	if (NULL != head1) dummy->mNext = head1;

	if (NULL != head2) dummy->mNext = head2;

	return dummyNode.mNext;

}

void BucketSort(int arr[], int n) {

	vector<ListNode*> buckets(BUCKET_NUM, (ListNode*)(0));

	for (int i = 0; i < n; ++i) {

		int index = arr[i] / BUCKET_NUM;

		ListNode *head = buckets.at(index);

		buckets.at(index) = insert(head, arr[i]);

	}

	ListNode *head = buckets.at(0);

	for (int i = 1; i < BUCKET_NUM; ++i) {

		head = Merge(head, buckets.at(i));

	}

	for (int i = 0; i < n; ++i) {

		arr[i] = head->mData;

		head = head->mNext;

	}

}

int main()

{

	int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };

	int len = (int) sizeof(arr) / sizeof(*arr);

	BucketSort(arr, len);

	for (int i = 0; i < len; i++)

		cout << arr[i] << ' ';

	cout << endl;

	return 0;

}

十大经典排序之桶排序（C++实现）的相关教程结束。