[Day29]程序菜鸟自学C++资料结构演算法 – 桶排序法(Bucket sort)

前言：桶排序又名箱排序，究竟这个特殊的排序法是怎麽运作的，让我们一来探讨！

桶排序：

和上一篇的基数排序一样是非比较型的排序法。运作原理通常是会先建立一些用来存放资料的桶子，每个桶子都有对应的资料区间，再将待排序的元素分别放到对应区间的桶内，并在桶内进行排序(在桶内的排序可以使用其他排序法，又或着可以用递回的方式继续执行桶排序)，最後在把桶内的元素取出就完成了，换言之，桶排序是用分析键值的分布来排序的。

执行效率分析：如果共有n个元素需要排序，而这些元素刚好都分散在不同的桶子中，也就是不必在桶内进行额外的排序，这实是最理想的状况，时间复杂度为O(n+m)(m用来表示桶子的数量)；但如果所有的元素都在一个桶内，则为最差的情况，时间复杂度为O(n^2)。

必须使用桶来暂时存放资料，所以需要用到额外的记忆体空间。属於稳定性的排序法，因为元素要分别放入桶内进行排序，所以相同键值的元素，排序後相对位置不会改变。

桶排序实作：

可以看到成功输出两组数组，负数也能在排序范围。

各排序法的比较：最後来复习并比较一下有介绍过的排序法。

本日小结：总算完结了排序的部分，其实排序法远远不止这些，这些是在课堂上比较有接触到的才分享给大家，如果还有参加铁人赛，或许还有机会跟大家一起讨论，明天就没有要在讲新的东西了，纯粹跟大家分享铁人赛的心得和感想，感谢大家看到最後（〃＾∇＾）o

template <typename T>
void bucket_sort(vector<T>& data, const int bucket_num = 0) { //传入桶的数目作为参数
	T minValue = data[0], maxValue = data[0];
	for (int i = 1; i < data.size(); i++) { //求最大值最小值
		if (data[i] > maxValue)
			maxValue = data[i];
		if (data[i] < minValue)
			minValue = data[i];
	}
	int bucket_n = maxValue - minValue + 1; //设定系统默认的桶数
	if (bucket_num != 0)
		bucket_n = bucket_num; //如果系统有传回bucket_n，则将bucket_n设为桶数
	T interval = (maxValue - minValue) / (bucket_n - 1); //设定桶的区间
	//公式：区间=(最大值-最小值)/(桶数-1)

	vector<vector <T>>buckets(bucket_n);
	for (auto e : data) //计算桶内元素的下标，方便後续的交换
		buckets[(e - minValue) / interval].push_back(e);

	int k = 0;
	for (int i = 0; i < bucket_n; i++) {
		int bucketSize = buckets[i].size();
		if (bucketSize > 0) { //桶内至少有一个元素
			if (bucketSize > 1) { //桶内至少有两个元素，并进行排序
				insert_sort(buckets[i]);
			}
			for (int j = 0; j < bucketSize; j++) {
				data[k] = buckets[i][j]; //如果桶内元素大於2才要排序，否则直接取出
				k++;
			}
		}
	}
}