基数排序是一种非比较类排序,非比较类排序效率较高,但对于所给数据有较高的要求,且需要比比较类排序更大的空间,所排序元素必须有进制.

算法原理

给定一个无序的数组

1.确定最大位数（bit）： 遍历整个数组，找到其中的最大值，然后确定其位数，将位数记为bit。

2.创建桶和help数组： 准备10个桶（编号0到9）以及一个help数组，用于暂时存放排序后的元素。

3.根据位数入桶： 从最低位（个位数）开始，遍历数组中的每个元素，将每个元素根据当前位数放入对应的桶中。例如，如果当前位数是个位数，则将个位数为1的数放入编号为1的桶，个位数为2的数放入编号为2的桶，以此类推。

4.依次倒出桶内元素： 接下来，按照桶的编号从0到9的顺序，依次将每个桶中的元素倒出来，放入help数组中，保持桶内元素的相对顺序。

5.更新数组内容： 将help数组中的元素依次拷贝回原始数组，这时数组已经根据当前位数排好序。

6.递增位数： 重复步骤3到5，逐渐递增位数，直到达到最大位数bit。

7.排序完成： 当位数达到最大位数bit时，整个数组已经完全排序。

代码实现

由于传统的基数排序(桶排序)对于空间的占用过于大,所以在代码实现中使用计数排序的方法对其进行优化,不去定义过多的桶,有效节省内存使用空间.

#include<bits/stdc++.h>
using namespace std;


int getMaxBit(int arr[],int n){ // 用于寻找出数组内最大数,并返回最大数的位数
	int maxn = arr[0];
	for(int i = 0 ; i < n ; ++i){
		maxn = max(maxn,arr[i]); 
	}
// 找出最大数
	int res = 0;
	while(maxn > 1){
		maxn /= 10;
		res++;
	}//计算位数
	return res;
}
void radixsort(int arr[],int n){ // 基数排序
	const int radix = 10; // 定义进制 , 这里是十进制
	int output[n]; // help数组
	int bit = getMaxBit(arr,n); // 获取位数
	
	for(int exp = 1;  exp  < pow(10,bit)   ; exp *= 10){
 // 主要逻辑 , 最大的循环意为循环每一位 , 从个位到最高位
		int count[radix] = {0}; // 1. 初始化计数数组 count，用于记录每个桶内元素的数量
    	        for (int i = 0; i < n; i++) { // 2. 统计每个桶中的元素数量
        	    count[(arr[i] / exp) % radix]++;
   	 	}
   	 	
  	  	for (int i = 1; i < radix; i++) { //   3. 将 count 数组中的元素累加，得到每个桶的结束位置
  	    	    count[i] += count[i - 1];
   	 	}
    	        for (int i = n - 1; i >= 0; i--) { // 4. 从原数组 arr 中的最后一个元素开始，根据当前位数放入对应的桶
        	    output[count[(arr[i] / exp) % radix] - 1] = arr[i];
        	    count[(arr[i] / exp) % radix]--;
    	        }
    	        for (int i = 0; i < n; i++) { // 5.把此轮排序结果拷贝至原数组
        	arr[i] = output[i];
    	        }
	} 
	
	
	
}
int main(){
	int n ;
	random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<int> dis(0, 100000);
	cin >> n;
	int arr[n];
	for(int i = 0 ; i < n; ++i){
		arr[i] = dis(gen);
	}
// 生成随机数组
	for(int i = 0 ; i < n ; ++i){
		cout <<arr[i] << " ";
	}
	cout << endl;
	radixsort(arr,n);
	for(int i = 0 ; i < n ; ++i){
		cout <<arr[i] << " ";
	}
	return 0;
}

Mareep