3.基数排序

#include <vector>
#include <set>
#include <algorithm>

void ArrPrint(std::vector<int> const & arr){

	for (auto i : arr){
		printf("%d ", i);
	}
	printf("\n");
}
//iBase 桶数
void radixsort(std::vector<int> & arr,unsigned int iBase){
	
	if (0 == iBase)
		iBase = 10;

	int iExp = 1;  //将数据分配到桶内的依据位 1  1*iBase  1*iBase*iBase ...
	int iMax = *std::max_element(arr.begin(), arr.end());

	while (iMax / iExp > 0){

		std::vector<int> bucket,temp;
		bucket.resize(iBase);		//桶
		temp.resize(arr.size());	//临时数组,用于收集桶内数据

		for (auto i : arr){
			bucket[i / iExp%iBase]++;	//计算每个桶内数据个数
		}
		for (int i = 1; i < bucket.size(); i++)
			bucket[i] += bucket[i - 1];		// 为了收集桶数据,计算每个桶以及前面所有桶的数据个数总数
								// 也就知道 arr[i] 在收集桶内数据时,排第几
		for (int i = arr.size() - 1; i >= 0; i--){
			int iCount = bucket[arr[i] / iExp %iBase];	// 将数据划分到桶内后，
									//桶 arr[i] / iExp %iBase 自己以及前面一共有多少个数据
			temp[--iCount] = arr[i];			//如果某个桶本身已经前面的桶一共有 
								　　　　 //iCount个数字,则从第一个桶开始收集,
									//这个桶的做后一个数字在收集后数组的下标是 iCount-1
			bucket[arr[i] / iExp %iBase] = iCount;		// 桶内数据减一,基于这个原因, 
									//本循环要从n-1到0迭代,否则收集桶数据的temp下标计算错误
		}

		std::copy(temp.begin(), temp.end(), arr.begin()); //将收集的数据从新放入数组,用于下次分配

		printf("\nPASS   : ");
		ArrPrint(arr);
		iExp *= iBase;
	}
}

int main()
{

	std::vector<int> arr = { 521, 310, 72, 373, 15, 546, 385, 856, 187, 147 };
	printf("\nARRAY  : ");
	ArrPrint(arr);
	radixsort(arr,10);  //分成10个桶进行排序
	printf("\nSORTED  : ");
	ArrPrint(arr);

	return 0;
}