qidao123.com技术社区-IT企服评测·应用市场
标题:
基数排序
[打印本页]
作者:
tsx81428
时间:
2023-7-6 17:10
标题:
基数排序
最近又有个奇奇怪怪的题目，数据为 \(n \le 1 \times 10^7\)，并且还要用到排序，普通的排序肯定会超时，然后就发现了一种 \(O(n)\)
介绍
基数排序(Radix Sort)是桶排序的扩展，它是将整数按位数切割成不同的数字，然后按每个数位分别比较以此来排序。
说详细点，也就是将所有数字统一为同样的长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。然后从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
下面就用表格来做个详细的解释：
最开始的序列214135413435533345532421654431既然从小到大排序，那么先排个位。
排完个位后42
1
43
1
53
2
41
3
53
3
21
4
65
4
13
5
43
5
34
5
再排十位
排完十位后4
1
32
1
44
2
14
3
15
3
25
3
31
3
54
3
53
4
56
5
4最后再排百位
排完百位后
1
35
2
14
3
45
4
13
4
21
4
31
4
35
5
32
5
33
6
54这便是最后的序列。
过程
1.查找数组a的最大值，并求出最大值的位数，作为循环的次数
2.统计所有数字某一位，用个桶 \(ct\) 来记个数。
3.然后做个前缀和ct
+=ct[i-1]，那么每个数的某一位 \(x\) 的排名就应该在 \(ct[x-1]+1 \sim ct[x]\)。
4.然后按照上一次排序的结果，利用 \(ct\) 逐一放进另一个数组，再赋值到原来数组上。
5.重复进行（2）（3）（4）的操作。
代码
[code]int maxbit(int a[],int n){ int maxx=0; for(int i=1;i
欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/)
Powered by Discuz! X3.4