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

引言

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

传送门——【排序算法】基数排序哔哩哔哩bilibili，b站嫖的一个视频——用一分钟的时间生动演示了基数排序的可视化过程，建议先看视频再来看文章和代码，学习效果直接事半功倍！

基数排序

基数排序（Radix Sort）是一种非比较型的排序算法，它根据元素的各个位数来进行排序。基数排序适用于待排序元素的取值范围相对较小，且位数固定的情况下。

其实不论是计数排序、上一篇文章的桶排序还是这里的基数排序都用到了“桶”的概念，只是映射关系不一样（即将元素分到不同桶中时采取的策略不同）。

• 基数排序：根据键值的每位数字来分配桶；

• 计数排序：每个桶只存储单一键值；

• 桶排序：每个桶存储一定范围的数值；

基数排序的步骤：

1. 按位分配：将待排序数组中的元素按照个位（十位、、百位等）进行分配到不同的桶（或称为箱子）中。

2. 依次合并：按顺序将各个桶中的元素依次取出合并到原数组。

3. 重复步骤1、2、，在步骤1中，按照更高位进行分配。

基数排序的特点：

• 基数排序的时间复杂度：最坏情况下：O(m*n)， m代表“桶”的个数，一般是10。

• 基数排序适用于待排序元素的位数固定、取值范围相对较小的情况

代码实现

如果没有学过计数排序的佳人，建议先在本文最下方链接中找到计数排序去学习，因为思路和代码与计数排序大概一致。

#include<bits/stdc++.h>
using namespace std;
void radix_sort(vector<int>& arr) {
	int max = *max_element(arr.begin(), arr.end());
	// 获取最大数的位数d
	int d = 0;
	while (max) {
		max /= 10;
		d++;
	}
 
	int* count = new int[10];  // 计数器，也就是0~9共10个桶 
	int* tem = new int[arr.size()];  // 临时数组，和计数排序的临时数组作用一样 
 
	int radix = 1;
	for (int i = 0; i < d; i++) {// 可以看成进行了d次计数排序，以下代码和基数排序万分相像 
		// 每次将计数器清零
		for (int j = 0; j < 10; j++) {
			count[j] = 0;
		}
		for (int j = 0; j < arr.size(); j++) {
			// 计数，方便后续获得每个数的index 
			count[(arr[j] / radix) % 10]++;
		}
		for (int j = 1; j < 10; j++) {
			count[j] += count[j - 1];
		}
		for (int j = arr.size() - 1; j >= 0; j--) {
			// 将桶里的元素取出来 
			int index = count[(arr[j] / radix) % 10] - 1;
			tem[index] = arr[j];
			count[(arr[j] / radix) % 10]--;
		}
		for (int j = 0; j < arr.size(); j++) {
			arr[j] = tem[j];
		}
 
		radix *= 10;
	}
 
}
int main() {
 
	vector<int> arr = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
 
	radix_sort(arr);
 
	for (int nums : arr) {
		printf("%d ", nums);
	}
 
	return 0;
}

运行结果展示

 系列其他文章

十大经典排序算法复杂度、应用场景总结 | 插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序、桶排序、计数排序-CSDN博客

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

经典排序算法之计数排序|c++代码实现-CSDN博客

经典排序算法之堆排序详解|c++代码实现|什么是堆排序|如何代码实现堆排序-CSDN博客

经典排序算法之快速排序|c++代码实现|什么是快速排序|如何代码实现快速排序-CSDN博客

经典排序算法之归并排序|递归和迭代法代码均提供|c++代码实现|什么是归并排序|如何代码实现-CSDN博客

经典排序算法之希尔排序|c++代码实现||什么是希尔排序|如何代码实现-CSDN博客

经典排序算法之插入排序|c++实现|什么是插入排序|如何代码实现-CSDN博客

排序算法之选择排序|c++实现-CSDN博客

经典排序算法之冒泡排序|c++代码实现-CSDN博客