C++ 基数排序

基数排序的原理：

（1）首先，把整数通过求余的方式拆分成“个位、十位、百位、… ”；

（2）然后，统计每个整数的“个位、十位、百位、… ”出现的次数，之后把次数存到以“余数”为编号的桶子里；

（3）最后，通过一个整数出现的次数-1，从而算出正确顺序的位置，再把整数放进去，就有顺序了。

#include <iostream>
#include <stdlib.h>
using namespace std;

/*******************************************/
/*  基数排序
/******************************************/

/*设数组元素为X，
因为要统计个十百到高位，
所以要用求余公式：
  （1）个位数 =（X/1）%10;
  （2）十位数 =（X/10）%10;
  （3）百位数 =（X/100）%10;
  （4） ... ... ...
/**************************************/

int MaxDigit(int array[], int n)  //获取数组中最大元素有多少位
{
	int digit = 1;  //位数从个位开始
	int radix = 10; 
	for (int i = 0; i < n; i++)
	{
		while (array[i] >= radix)
		{
			radix = radix * 10;
			++digit;
		}
	}
	return digit;  //返回最大元素的位数
}


void RadixSort(int array[], int n)  //基数排序函数
{
	int digit = MaxDigit(array, n);
	int temp[6];  //这里以6个元素为例
	int buckets[10];  //数组元素的个、十、百位到高位都是在0~9之间，所以用10
	int base = 1;  //从个位开始
	int i, j, k;

	for( i  = 1; i <= digit; i++)
	{	
		for (j = 0; j < 10; j++)
		{
			buckets[j] = 0;  //初始化buckets[]数组
		}

		for (j = 0; j < n; j++)
		{
			k = (array[j] / base) % 10;  //求余
			buckets[k]++;  //把次数存储到以求余为编号的水桶内，假如余数是5，开始次数buckets[5] = 0, ++后存1次
		}
		    
		for (j = 1; j < 10; j++)
		{
			buckets[j] = buckets[j - 1] + buckets[j];  //统计存储在水桶里元素的总次数
		}

		for (j = n - 1; j >= 0; j--)
		{
			k = (array[j] / base) % 10;  //求余
			temp[buckets[k] - 1] = array[j];  //把array[]数组元素赋给已经排好位置的temp[]数组
			buckets[k]--;  //水桶里元素的总次数减少
		}

		for (j = 0; j < n; j++)
		{
			array[j] = temp[j];  //将排好顺序的元素赋给array[]数组
		}

		base = base * 10;  //个位变十位变百位变高位，所以乘以10
		
	}
}


int main(void)  //主程序
{
	const int n = 6;  //数组元素的数量
	int array[n];
	cout << "请输入6个整数：" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> array[i];
	}

	cout << endl;  //换行

	RadixSort(array, n);  // 调用RadixSort函数  进行排序

	cout << "由小到大的顺序排列后：" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << "Array" << "[" << i << "]" << " = " << array[i] << endl;
	}

	cout << endl << endl;  //换行

	system("pause");  //调试时，黑窗口不会闪退，一直保持
	return 0;
}

运行结果：