编辑代码

#include <iostream>

using namespace std;

int findMax(int arr[],int len){
	int max = arr[0];
	for (int i=0;i<len;i++){
		if(arr[i]>max){
			max=arr[i];
		}
	}
	return max;
}
//输入50，返回2
//输入100，返回3 
int calBitCount(int max){
	int bit=0;
	while(!max){
		max /= 10;
		bit++;
	}
	return bit;
}
// 输入（50，0），返回0
// 输入（50，1），返回5 
int getBitValue(int value,int bit){
	for(int i=0;i<bit;++i){
		value /= 10;
	}
	return value%10;
}

void radixSort(int arr[],int len){
	//1. 找出最大值，计算出需要排序的位 
	int max = findMax(arr,len);
	int bitCount = calBitCount(max);
	//2. 创建排序数组
	int radixCount = 10;
	int* tempArray = new int[len]();
	int* count = new int[radixCount]();
	//3. 对每一位进行排序
	for (int b=0;b<bitCount;++b){
		//3.1 清空排序数组,把每个值赋予0
		for (int k = 0;k<len;++k){
			arr[k]=0;
		}
		
		//3.2 统计计数数组下标对应元素个数
		for (int i = 0;i<len;++i){
			int bitValue = getBitValue(arr[i],b);
			++count[bitValue];
		}
		
		//3.3 累计算出小于等于计数数组下标对应元素的个数 
		for (int c = 1;c<radixCount;++c){
			count[c] += count[c-1];
		}
		
		//3.4 利用累加值和临时数组对对应的位进行排序
		for (int i=len-1;i>=0;--i){
			int bitValue = getBitValue(arr[i],b);
			tempArray[count[bitValue]]=arr[i];
		}
		
		// 3.5 临时数组数据拷贝回原数组
		for (int i=0;i<len;++i){
			arr[i]=tempArray[i];
		}
	}
}

void printArray(int arr[], int len) {
	for (int i = 0;i<len;++i){
		cout << arr[i] << " ";
	}
	cout << endl;
}

int main(){
	int arr[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48,};
	int len = sizeof(arr)/sizeof(int);
	
	printArray(arr,len);
	radixSort(arr, len);
	printArray(arr,len);
}