基数排序
本帖最后由 bangbang-ande 于 2023-7-12 20:13 编辑基数排序——基数排序也是计数排序的升级版，这一个排序的方法很巧妙，相信听完这一部分之后一定有收获。
基数排序依旧有桶排序的影子，同样需要用到桶：
https://cdn.luogu.com.cn/upload/image_hosting/j8h34m7p.png
但是基数排序的桶的数量是固定的，就是10个桶。我们讲的时候大家就明白了。
举一个例子：
下标012345678 9
a[] 94 27 12 9 125 30 55 40 73 65
第一步，初始化，建立10个桶+将数字存入数组中
https://cdn.luogu.com.cn/upload/image_hosting/e0lyefta.png
第二步，我们先看每一个数的个位，把个位的值对应到相同的数字中：（这里所使用的存法是链表，但实际打代码的时候可以不用用链表）
https://cdn.luogu.com.cn/upload/image_hosting/49c3dx2o.png
然后下一步也很简单，将我们放在桶中的数据重新放回数组中，此时有人问：怎么放呢？其实是这样的：我们将桶从小到大循环，将桶中的数据依照放入的顺序重新放入数组中，然后清零桶，得到这样子：
https://cdn.luogu.com.cn/upload/image_hosting/82xk4z92.png
此时已经完成了第一次操作，但实际上大家可能没有发现排完的数据有序在哪里，那我们继续进行第二次相同的操作，但注意，我们接下来比对十位，如果数只有一位，那就十位是0。同样将对应数字加入桶中：
https://cdn.luogu.com.cn/upload/image_hosting/jprv02vz.png
下一步同样类比操作，存入数组中，存后的图如下：
https://cdn.luogu.com.cn/upload/image_hosting/ir1x945n.png
此时的程序就基本有序了，然后继续进行操作，下一步的操作大家自行完成。最后就得到一个排好序的序列了。
这就是基数排序的做法了，总结下来就3步：第一步从个位数开始循环，循环到所有位数都循环完，然后在循环内部进行两步操作，一步是将对应数字加入桶中，第二步是将桶里的数字从小到大重新取回数组中。
接下来我们根据这几步写出来核心代码：
//这一部分可在附件中看到
整一段代码分为三部分：
1-4为第一部分，6-16为第二部分，18-25是第三部分
这三部分的大概作用其实在注释中已经说明得很清楚了。
解决一下注释中的两个问题：
Q1：这一段的内容其实是找出这个数的某一位。无论是个位，十位，百位，找法都是这样子，大家可以代入几个数字试一试，就可以明白了
Q2：这段代码一定不能删，因为如果不删去，之前的数字残留，会影响到下一次的遍历
所以这段代码的讲解就大约这样子。
接下来是完整代码：
//这一部分可在附件中看到
最后说说该排序的特性：
1. 一样的，本排序一定是不稳定排序，理由是运用了计数排序的做法，当然是不稳定的排序
2. 本排序的时间复杂度为O(n+n log lmax)≈O(n)，推断方法很简单：
加入对应桶中的时间复杂度为O(n\log lmax)，而将排好的桶放在数组中的时间复杂度为O(n)
所以时间复杂度为O(n+n log lmax) 之前我写过基数排序，现在除了在卡常的时候都不会用{:10_306:} 上一个比较拙劣的基数排序：
int getw(int num, int w)
{
while (--w)
num /= 10;
return num % 10;
}
void rsort(int * a,int len)
{
static int tmp;
int maxnum = -1 << 30, w = 0;
for (int i = 0; i < len; ++i) maxnum = max(maxnum, a);
while (maxnum) {
maxnum /= 10;
w++;
}
for (int i = 1; i <= w; ++i) {
int cnt = {};
for (int j = 0; j < len; ++j)
cnt, i)]++;
for (int i = 1; i < 10; ++i)cnt += cnt;
for (int j = len - 1; j >= 0; --j)
tmp[--cnt, i)]] = a;
for (int i = 0; i < len; ++i)
a = tmp;
}
}
1 年前写的代码，好丑{:10_256:}
页:
[1]