基数排序

缘起

【1】和【2】分别介绍了非比较排序的桶排序和计数排序两种算法. 两种算法的缺点无疑就是空间复杂度太高——万一空间卡的比较死，然后参与排序的数值分布比较稀疏的话, 时间复杂度和空间复杂度都会较高. 而基数排序结合了桶排序的特点，但是空间复杂度不高. 对比桶排序，基数排序每次需要的桶的数量并不多。而且基数排序几乎不需要任何“比较”操作，而桶排序在桶相对较少的情况下，桶内多个数据必须进行基于比较操作的排序。因此，在实际应用中，基数排序的应用范围更加广泛。

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include "stdafx.h"
#include <iostream>
#include <queue>

#pragma warning(disable:4996)


//#define LOCAL
using namespace std;

void radix(int *a, int n) // 基数排序
{
	queue<int> q1[10];
	queue<int> q2[10]; // 此算法需要两个队列, 因为需要从一个队列导到另一个队列去, 10 表示0~9

	for (int i = 0; i<n; i++) // 个位
	{
		q1[a[i]%10].push(a[i]);
	}

	for (int i=  0; i<10; i++) // 十位, 注意，一定要按照 0~9 顺序进行才行
	{
		while(!q1[i].empty())
		{
			int tmp = q1[i].front();
			q1[i].pop();
			q2[tmp/10%10].push(tmp);
		}
	}

	for (int i = 0; i<10; i++) // 百位, 注意, 也一定要按照 0~9 顺序才行
	{
		while(!q2[i].empty())
		{
			int tmp = q2[i].front();
			q2[i].pop();
			q1[tmp/100%10].push(tmp);
		}
	}

	puts("排序后");
	for (int i = 0; i<10; i++) // 最后排好序的数字就在q1中, 也要按照 0~9 的顺序
	{
		while(!q1[i].empty())
		{
			printf("%d ", q1[i].front());
			q1[i].pop();
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif

	int a[12]={278,109,63,930,589,184,589,505,269,8,83,63};  // 本例以不超过3位数的正整数序列排序为例, 如果是不超过四位数的话. 就要多倒几次
	radix(a,12);
	return 0;
}

为什么上述程序是可行的? 因为你想啊, 最后q1是按照百位数从高到低的. 所以q1[1]中的任何一个数字一定大于q1[0]中的数字, 因为q1[1]中任何一个数字的百位数字是1, 而q1[0]中的任何一个数字的百位数字是0. 那么q1[i]中的数字怎么保证后进入队列的十位数就一定高于先进入队列的十位数字呢? 别忘了, q2是按照 q2[0]~q2[9]这样出队列的. 所以q1[i]中后进入队列的数字的十位数字一定大于先进入队列的十位数字. 如果十位数字也一样，怎么保证前面的个位数字后进队列的比前进队列的要>=呢? 别忘了, 最初个位数字从q1出栈进入q2是按照 0~9的顺序的. 所以能保证这一点. 从这点看, 基数排序不仅快，而且空间复杂度也很小. 设计很精妙的.

参考

【1】https://yfsyfs.github.io/2019/05/25/%E9%9D%9E%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F%E4%B9%8B%E6%A1%B6%E6%8E%92%E5%BA%8F/

【2】https://yfsyfs.github.io/2019/05/25/%E9%9D%9E%E6%AF%94%E8%BE%83%E6%8E%92%E5%BA%8F%E4%B9%8B%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F/