浅显易懂的桶排序

想准备将所有的排序算法都总结出来，方便你查阅，也方便我复习和记忆，下面来说桶排序：

首先必须申明，桶排序和计数排序完全不同，不可混为一谈：（这里实例用单链表来操作）

还是老方法，看文字就是烦，直接上图，图文结合，永远都是王道：

1.假设：桶待排序列：{ 49, 38, 35, 97, 76, 73, 27, 49 ,34,78}

看了之后有没有特莫感觉就是哈希桶，哈哈，满足一定条件差不多就是啦；言归正传，key值就是待排序序列，Bucket为桶，数据按某种函数，映射到桶中

2.关于映射及桶排原理分析：

桶中数据的十位都一样，那么映射函数算出的桶号就是这些数据的十位，也就是说，这种映射函数，目的就是为了找出数据的共同特点，可能是求余（哈希表直接定址，就是这样），可能是除某数求商，本例中就是取商；

即就是所有数据除某数取得的商相同的都放一个桶中，如图中的3号桶，刚开始，3号桶中的数据是无序的，第一遍操作，只能保证这些数据一定是在这个桶中，

但是桶中的顺序还是要排的，之后，遍历一遍桶，输出即就是一个有序序列，就这几句话，我感觉说完了，至于更深层的剖析，稍后再说，先来代码：

#pragma once

//每一个节点的结构
struct node
{
	int key;  //关键字，在桶中统计桶中数据量，在数据节点中就是节点的数据
	struct node *next;
};

//声明：
void PrintBucketSort(node** bucket, int bucket_size);
int f(int x);

void BucketSort(int* a, int size,int bucket_size)
{
	assert(a);
	
	//给桶申请空间
	node** bucket = new node*[bucket_size*sizeof(node)]; 

	//初始化
	for (int i = 0; i < bucket_size; ++i)
	{
		bucket[i] = new node[sizeof(node)]; //每一个桶
		bucket[i]->key = 0;
		bucket[i]->next = nullptr;
	}

	for (int j = 0; j < size; ++j)
	{
		node* sub_node = new node[sizeof(node)]; //桶下的每一个节点
		sub_node->key = a[j];
		sub_node->next = nullptr;

		//计算这数据在哪个桶中
		int num = f(a[j]);

		//让一个指针指向这个桶号的头
		node* sub_head = bucket[num];

		//开始插入
		if (sub_head->next == nullptr)
		{
			bucket[num]->next = sub_node;
			bucket[num]->key++;
		}
		//该桶号不为空，那么插入排序
		else
		{
			while (sub_head->next != nullptr && sub_node->key >= sub_head->next->key)
			{
				sub_head = sub_head->next;
			}

			sub_node->next = sub_head->next;
			sub_head->next = sub_node;
			bucket[num]->key++;
		}
	}
	//打印
	PrintBucketSort(bucket, bucket_size);
}

//映射函数
int f(int x)
{
	return (x / 10);
}

//打印
void PrintBucketSort(node** bucket, int bucket_size)
{
	//多少桶链(桶号)
	for (int i = 0; i < bucket_size; ++i)
	{
		node* cur = bucket[i]->next;
		while (cur)
		{
			cout << cur->key << " ";
			cur = cur->next;
		}
	}
	cout << endl;
}

void Test7()
{
	int a[10] = { 49, 38, 35, 97, 76, 73, 27, 49, 34, 78 };
	cout << "桶排序" << endl;
	BucketSort(a, 10, 10);  //桶数据最大才97，所以需要10个桶
}

哎呀，敲了我十几分钟，看看结果：

第一个就是排序，第二个就是数据在桶中的分布，横行代表桶，10个桶，没有数据的桶是0；

桶排序就是这样：

对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：

O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。

桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。

当然桶排序的空间复杂度为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。

此外，桶排序是稳定的。

赐教！