算法:基数排序

基数排序是桶排序的一种,属于稳定性的排序。

例题

洛谷1177 排序

题目描述
将读入的 N 个数从小到大排序后输出。

输入格式
第 1 行为一个正整数 N。
第 2 行包含 N 个空格隔开的正整数 a[i],为你需要进行排序的数,数据保证了a[i]不超过10^9。

输出格式
将给定的 N个数从小到大输出,数之间用空格隔开。

输入输出样例
输入

5
4 2 4 5 1

输出

1 2 4 4 5

说明提示
对于20% 的数据,有 N <= 10^3。
对于100% 的数据,有 N <=10^5 。

基数排序

基数排序往往都用每位上的数字来排序,但这样就只能对非负整数进行排序了(之所以此题能用基数排序AC,就是因为所有的数据中没有负数,否则就崩了)。算法是先依据每个元素的个位上的数字进行桶排序,即开一个数组base[i][j]表示第j个个位数字为i的数的值,之后按i从0到9的顺序再将这些数放回原数组中。接着再去按十位、百位、千位这么排下去直到排到的位数是数组中最大元素的位数时,就排序完成了。

举个例子,方便理解。
初始状态:712,303,4,18,89,999,70,26
第一次按个位排序:070,712,303,004,026,018,089,999
第二次按十位排序:303,004, 712,018,026, 070,089,999
第三次按百位排序:004,018,026,070,089,303,712,999

最后算一下算法时间复杂度:三重循环,第一重循环的是位数digit(这里digit表示a数组中最大元素的位数,又因为a数组是int类型的,所以digit连10都没到,是个很小的数),第二重循环加上第三重循环总共也就n次,所以时间复杂度为O(digit * n)级别,速度极快无比。

代码

# include <cstdio>
# include <algorithm>
# include <cmath>
# include <cstring>

using namespace std;

const int N_MAX = 100000;

int n;
int a[N_MAX + 10];
int base[10][N_MAX + 10];

int countMaxDigit(){
	int cnt = 0, num = 0;
	for (int i = 1; i <= n; i++)
		num = max(a[i], num);
	while (num != 0) {
		cnt++;
		num /= 10;
	}
	if (cnt == 0) cnt = 1; // 如果说num = 0,那么位数也应当是1 
	return cnt;
}

void radixSort()
{
	int digit = countMaxDigit(), ten = 1;
	for (int t = 1; t <= digit; t++) {
		memset(base, 0, sizeof(base));
		for (int i = 1; i <= n; i++) {
			int num = a[i] / ten % 10;
			base[num][++base[num][0]] = a[i]; // 这里直接用base[num][0]表示base[num]中元素的个数了
		}
		int now = 0;
		for (int i = 0; i <= 9; i++)
			for (int j = 1; j <= base[i][0]; j++)
				a[++now] = base[i][j];
		ten *= 10;
	}
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	radixSort();
	for (int i = 1; i <= n; i++)
		printf("%d ", a[i]);
	printf("
");
	return 0;
}
原文地址:https://www.cnblogs.com/000zwx000/p/12330710.html