经典排序算法之桶排序详解|c++代码实现|简单易懂

甫为964

1884人浏览 · 2024-03-15 15:10:13

甫为964 · 2024-03-15 15:10:13 发布

引言

排序算法c++实现系列第9弹——桶排序。该系列文章主要讲解了十大经典排序算法，如最基础的冒泡排序、选择排序到借助堆数据结构实现的堆排序，其余所有算法的文章在本文最后都有链接，感兴趣的uu可以移步支持。如果本系列文章对你有所启发的话，还请麻烦点赞&关注咯。如果可以的话，其实留下一个关注以防走丢也不是不可以，谁叫咱有缘分相遇了呢，嘻嘻嘻。

传送门——【排序算法】桶排序哔哩哔哩bilibili，一个三十秒的短视频，生动演示了桶排序的可视化过程，建议先看视频再来看文章和代码，学习效果直接事半功倍！

桶排序

桶排序（Bucket Sort）是计数排序（文末有链接）的升级版，它根据映射关系将待排序数组分割成若干个桶（或称为箱子），每个桶内的元素具有相同的范围。然后对每个桶内的元素进行排序，最后将所有桶中的元素按照顺序依次合并，得到排序后的结果。

为了提高算法的效率和稳定性，我们通常需要尽可能的将所有元素均匀的分配到每个桶中，这就涉及到映射关系的选择。同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。文末也有一篇介绍十大经典排序算法的优缺点、使用场景等的学习笔记，uu们可以自行食用。

桶排序的步骤：

划分桶：根据待排序数组的特点，将其划分成若干个桶，每个桶表示一个范围区间，桶的数量可以根据问题的要求来确定。
分配元素：遍历待排序数组，将每个元素根据其值的范围分配到相应的桶中。
对每个桶进行排序：对每个桶中的元素进行排序，可以选择合适的排序算法，如插入排序、快速排序等。
合并桶：将所有桶中的元素按照顺序依次合并，得到排序后的结果。

桶排序的特点：

桶排序的时间复杂度取决于对每个桶内元素进行排序的时间复杂度，理想情况下可以达到线性时间复杂度。
桶排序适用于待排序数组的取值范围较小且分布比较均匀的情况。

代码实现

#include<bits/stdc++.h>
using namespace std;
void bucket_sort(vector<int> &arr) {
	int n = arr.size();
	if (n <= 1) return;

	// max_element()查找给定范围内的最大值，返回指向最大值的迭代器，用*取出数据
	int maxVal = *max_element(arr.begin(), arr.end());
	int minVal = *min_element(arr.begin(), arr.end());
	int bucketSize = maxVal - minVal + 1;
	int bucketCount = 10; // 桶的数量

	vector<vector<int>> bucket(bucketCount);

	// 将元素分配到桶中
	for (int num : arr) {
		int index = (num - minVal) * bucketCount / bucketSize;  // 均匀分布哈哈哈 
		bucket[index].push_back(num);
	}

	// 对每个桶中的元素进行排序（可以使用任何一种排序算法）,这里偷懒直接用了STL中的sort()
	for (auto& b : bucket) {
		sort(b.begin(), b.end());
	}

	// 将排序后的元素依次放回原数组
	int index = 0;
	for (auto& b : bucket) {
		for (int num : b) {
			arr[index++] = num;
		}
	}
}

int main() {

	vector<int> arr = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
	bucket_sort(arr);
	for (int nums : arr) {
		printf("%d ", nums);
	}
	return 0;
}