编辑代码

#include <iostream> 

using namespace std;

//找数组中的最大值 
int findMax(int arr[], int len) {
	int max = arr[0];
	for(int i = 1; i < len; ++i) {
		if (arr[i] > max) {
			max = arr[i];
		}
	} 
    return max;
}

//计算传入的数组中的最大值的位数，决定要进行多少位的排序 
//输入50，返回2
//输入100，返回3
int calBitCount(int max) {
    int bitCount = 0;
    while(1) {
    	if(max == 0) {	//max每次除10，最后max为0时即为除完max的所有位 
            break;
        }  
        max = max/10;
        bitCount++;		//max每次除10，位数增1
    }
	return bitCount;
} 

//计算value指定的位bit的值
//输入（50，0），返回0
//输入（50，1），返回5
int getBitValue(int value, int bit) {
	for(int i = 0; i < bit; ++i) {		//通过循环，将指定的位bit变为个位 
		value = value/10;
	} 	
    return value%10;					//指定的位bit为个位后，取余10则可以得到其值 
}

void radixSort(int arr[], int len) {
	//1.找出最大值，计算出需要排序的位
	int max = findMax(arr, len);		//找数组中的最大值 
	int bitCount = calBitCount(max);	//计算数组中的最大值的位数，之所以找最大值是因为其位数能满足数组中其他数据所需的位数	

	//2.创建排序数组
    int radixCount = 10;				//每一位的取值为0-9，所以需要计数数组长度为10 
    int* count = new int[radixCount]();	//创建计数数组 
    int* tempArray = new int[len]();	//创建临时数组，存放每一位排好序的数据 

    //3.对每一位进行排序
    for(int b = 0; b < bitCount; ++b) {
        //3.1 清空排序数组（初始化） 
        for (int c = 0; c < radixCount; ++c) {
            count[c] = 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] + count[c-1];
        }
        //3.4利用累加值和临时数组对应的位进行排序
        for(int i = len - 1; i >= 0; --i) {
            int valueIndex = getBitValue(arr[i], b);	//获取原数组中元素在计数数组中的下标 
            --count[valueIndex];						//由于计数数组存放的值是排好序的元素的下标加1，所以需要减1
            tempArray[count[valueIndex]] = arr[i];		//将原数组的元素存放到临时数组，其在临时数组的位置是已排好序的 
        }
        //3.5临时数组数据拷贝回原数组，以便进行下一位的排序 
        for(int i = 0; i < len; ++i) {
            arr[i] = tempArray[i];
        }
    }
    //内存清理
    delete tempArray;
    delete count;
}

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

int main(){
	//1.最大值位数为2 
	int arr[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
	int len = sizeof(arr)/sizeof(int);
	cout << "排序前：";
	printArray(arr, len);
	radixSort(arr, len);
	cout << "排序后："; 
	printArray(arr,len);
	
	//2.最大值位数为3 
	int arr2[] = {126,69,593,23,6,89,54,8};
	int len2 = sizeof(arr2)/sizeof(int);
	cout << "排序前：";
	printArray(arr2, len2);
	radixSort(arr2, len2);
	cout << "排序后："; 
	printArray(arr2,len2);
	

}