基数排序

也是采用分桶的思想，但是加入了按位比较的思想（可以理解为每位进行一次计数排序）

思路：

计算数列中最大位数
按位数循环处理每位的排序

代码实现：

#include<iterator>

#include<iostream>

#include<vector>

using namespace std;

int maxbit(int data[], int n) //辅助函数，求数据的最大位数

{

	int d = 1; //保存最大的位数

	int p = 10;

	for (int i = 0; i < n; ++i)

	{

		while (data[i] >= p)

		{

			p *= 10;

			++d;

		}

	}

	return d;

}

void RadixSort(int data[], int n) //基数排序

{

	int d = maxbit(data, n);

	vector<int> tmp(n);

	vector<int> count(n);//计数器

	int i, j, k;

	int radix = 1;

	for (i = 1; i <= d; i++) //进行d次排序

	{

		for (j = 0; j < 10; j++)

			count[j] = 0; //每次分配前清空计数器

		for (j = 0; j < n; j++)

		{

			k = (data[j] / radix) % 10; //统计每个桶中的记录数

			count[k]++;

		}

		for (j = 1; j < 10; j++)

			count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶

		for (j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中

		{

			k = (data[j] / radix) % 10;

			tmp[count[k] - 1] = data[j];

			count[k]--;

		}

		for (j = 0; j < n; j++) //将临时数组的内容复制到data中

			data[j] = tmp[j];

		radix = radix * 10;

	}

}

int main()

{

	int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };

	int len = (int) sizeof(arr) / sizeof(*arr);

	RadixSort(arr, len);

	for (int i = 0; i < len; i++)

		cout << arr[i] << ' ';

	cout << endl;

	return 0;

}

参考资料：https://baike.baidu.com/item/基数排序

十大经典排序之基数排序（C++实现）的相关教程结束。