桶排序

时间复杂度

因为时间复杂度度考虑的是最坏的情况，所以桶排序的时间复杂度可以这样去看(只看主要耗时部分，而且常熟部分K一般都省去)

N次循环，每一个数据装入桶
然后M次循环，每一个桶中的数据进行排序(每一个桶中有N/M个数据)，假设为使用比较先进的排序算法进行排序
一般较为先进的排序算法时间复杂度是O(N*logN)，实际的桶排序执行过程中，桶中数据是以链表形式插入的，那么整个桶排序的时间复杂度为:

O(N)+O(M*(N/M)log(N/M))=O(N(log(N/M)+1))
所以，理论上来说(N个数都符合均匀分布)，当M=N时，有一个最小值为O(N)

空间复杂度

空间复杂度一般指算法执行过程中需要的额外存储空间

桶排序中，需要创建M个桶的额外空间，以及N个元素的额外空间

所以桶排序的空间复杂度为 O(N+M)

稳定性

稳定性是指，比如a在b前面，a=b，排序后，a仍然应该在b前面，这样就算稳定的。

桶排序中，假如升序排列，a已经在桶中，b插进来是永远都会a右边的(因为一般是从右到左，如果不小于当前元素，则插入改元素的右侧)

所以桶排序是稳定的

PS:当然了，如果采用元素插入后再分别进行桶内排序，并且桶内排序算法采用快速排序，那么就不是稳定的

const int BUCKET_NUM = 20;
struct ListNode {
	ListNode *next;
	int val;
	ListNode(int x) :val(x), next(NULL) {}
};
ListNode* merge(ListNode *node1,ListNode* node2) {
	if (node1 == nullptr) return node2;
	if (node2 == nullptr) return node1;
	ListNode dummy(-1);
	ListNode *cur = node1;
	cur = &dummy;
	while (node1 != nullptr && node2 != nullptr) {
		if (node1->val <= node2->val) {
			cur->next = node1;
			node1 = node1->next;
		}
		else {
			cur->next = node2;
			node2 = node2->next;
		}
		cur = cur->next;
	}
	cur->next = node1 == nullptr ? node2 : node1;
	return dummy.next;
}
ListNode* insert(ListNode* head,int val) {
	ListNode dummy(-1);
	dummy.next = head;
	ListNode *nowNode = new ListNode(val);
	ListNode* pre = &dummy;
	ListNode* cur = head;
	while (cur != nullptr && cur->val <= val) {  //要加等号 不然变成了不稳定的排序
		pre = cur;
		cur = cur->next;
	}
	nowNode->next = cur;
	pre->next = nowNode;
	return dummy.next;
}
void bucketSort(int arr[], int n) {
	vector < ListNode* > bucket(BUCKET_NUM, (ListNode*)(0));
	for (int i = 0; i < n; i++) {
		int index = arr[i] / 10;
		ListNode* head = bucket[index];
		bucket[index] = insert(head, arr[i]);
	}
	ListNode* head = bucket[0];
	for (int i = 1; i < n; i++) {
		head = merge(head, bucket[i]);
	}
	for (int j = 0; j < n; j++) {
		arr[j] = head->val;
		head = head->next;
	}
}
int main(void) {
	int nums[20] = { 40,28,8,5,1,80,62,49,74,92,91,99,1,15,22,39,20,5,81,60 };
	bucketSort(nums, 20);
	for (int i = 0; i < 20; i++) {
		cout << nums[i]<<endl;
	}
	return 0;
}