编辑代码

#include <iostream>

using namespace std;

void printArray(int arr[], int len);
int findMax(int arr[], int len) {
	int max = arr[0];
	for (int i=1; i<len; ++i) 
		if (max < arr[i]) max = arr[i];
	return max;
}

//输入50，返回2
//输入100，返回3 
int calBitCount(int max) {
	int count = 0;
	for (; max/=10; ++count);
	return count+1;
}

// 输入（50，0），返回0
// 输入（50，1），返回5 
int getBitValue (int value, int bit) {
	for (; bit>0; --bit)
		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 *count = new int[radixCount]();
	int *tempArray = new int[len]();
	
	//3. 对每一位进行排序 
	for (int b = 0; b < bitCount; ++b) {
		//3.1 清空排序数组,把每个值赋予0 
		for (int i=0; i<radixCount; ++i) count[i] = 0;
		for (int i=0; i<len; ++i) tempArray[i] = 0;
		
		//3.2 统计计数数组下标对应元素个数
		for (int i = 0; i < len; ++i)
			++count[getBitValue(arr[i], b)];
		
		//3.3 累计算出小于等于计数数组下标对应元素的个数 
		for (int c = 1; c < radixCount; ++c)
			count[c] += count[c-1];

		//3.4 利用累加值和临时数组对对应的位进行排序
		for (int i=len-1; i>=0; --i)
			tempArray[--count[getBitValue(arr[i], b)]] = arr[i];

		// 3.5 临时数组数据拷贝回原数组
		for (int i=0; i<len; ++i)
			arr[i] = tempArray[i];

 	}
 	
	delete count;
	delete tempArray;
}