【写在之前】
由于最近要写后缀数组 以及要给高一讲课
所以就写了这个。。。。。。
【正式开始】
计数排序(≠桶排序)
计数排序的算法显然更加高明 $ O(n+MAX\ NUM)$
int n,maxn;
int num[N],key[MAX_NUM],rank[N];
for(int i=1;i<=n;++i) read(num[i]),key[num[i]]++,maxn=max(maxn,num[i]);
for(int i=1;i<=maxn;++i) key[i]+=key[i-1];
for(int i=n;i;--i) rank[key[num[i]]--]=num[i];
最后的rank数组就是排好序的数组
1.为什么要计算前缀和 ?
因为利用前缀和 我们就可以实现 快速排名查询
例如我们有这样一组数据
1 10 10 2 2 8 3 3 6 5
那么我们这样的话 就可以实现快速查询排名
2.为什么我们倒叙收集嘞 ?
这就涉及到了排序算法的【稳定性问题】
我们例如我们有这样一组数据 TA们每一个都具有两个属性\(X,Y\)
现在 我们需要定义\(X\)为优先级 进行排序
排完序之后 有两种结果
有木有什么不同呢 ？ ？ ？
没错 我们确实是定义了比较的优先级
但是第一种结果未改变Y的原始顺序 第二种结果却改变了
没错 稳定性就是
一个序列中的每一个元素 可能存在多种属性
我们希望在对一个属性排序的同时 尽量不改变其他属性的性质 最常见的就是读入顺序
这就是排序算法的稳定型问题
一般来讲
稳定的排序有: 冒泡排序 二路归并排序 二叉树排序 插入排序 桶排序 计数排序 基数排序
不稳定的排序有: 直接选择排序 希尔排序 快速排序 堆排序
有跨度的排序一般都是不稳定的
我们是从\(1\)到\(n\)是数进桶的
然后 肯定是后面的后进桶 这时桶就成了一个栈
如果我们还是正序收集的话 后面的数就被收集进来 那么就打乱了原来的读入顺序
这就是 不稳定的排序了 ！ ！ ！
所以我们需要倒序收集
Q : 一般来讲的话 数列中的元素仅需维护一个值即可 这里正序倒序是不是没有关系 ? ? ?
A : Yes 但是很可惜 接下来的算法要求你必须使用倒序收集
基数排序
基数排序 就是对于数的每一个数位进行排序
比如说 我先按照个位 再按照十位 再按照百位 再按照千位......
有两种表现形式 LSD(由低位向高位) MSD(由高位向低位)
一般来讲LSD的性能远远优于MSD
同时由于本蒟蒻比较菜 所以只介绍LSD
看完Gif之后应该都已经透彻了吧
#define IL inline
#define R register
int deep,n,maxn;
int cnt[15],num[N],tmp[N];
IL int ready()//获取最高数位
{
int sum=1,now=1;
while(now<=maxn)
{
now*=10;
sum++;
}
return sum-1;
}
IL void Jsort()
{
deep=ready();int now=1;
for(R int i=1;i<=deep;++i)
{
memset(cnt,0,sizeof cnt);//桶一定要清空
// printf("now -> %d\n",now);
for(R int j=1;j<=n;++j) cnt[(num[j]/now)%10]++;//对于当前数位开桶收集
for(R int j=1;j<=10;++j) cnt[j]+=cnt[j-1];//同计数排序
for(R int j=n;j;--j)
tmp[cnt[(num[j]/now)%10]--]=num[j];
for(R int j=1;j<=n;++j) num[j]=tmp[j];
// for(R int i=1;i<=n;++i) printf("%d%c",num[i],(i==n ? '\n':' '));
now*=10;
}
return;
}
Q : 为什么这里必须要使用倒序收集 ？ ？ ？
A : 因为在这里 我们把当前数位作为优先级 但是相同的情况下 应该怎么办? ? ?
应该是按照上一优先级 比如说我们比较两个数的大小 一般是先比较高位 高位相同的话比较次高位也就是低位 以此类推
那么这里 因为是LSD 所以我们对于当前为相同的数 就是应该按照上一位的优先级比
又因为上一位的优先级顺序我们已经处理过了 所以我们仅需再次维护即
所以这里就需要计数排序的稳定性
我们希望在遵守当前优先级的情况下 尽量去维护上一优先级的原始顺序
也就是所谓的"读入顺序" 只不过这里成了一个二手顺序
这样的话 对于同一高位的数 就可保持原来地位的顺序
比如说
38 48 47 37
我们先按照个位排好序
47 37 38 48
然后是十位 可是十位存在相同位怎么办
我们先倒序收集 排好序之后是这个样子
37 38 47 48
倒序收集在遵守十位优先的情况下 保持了原来个位的顺序
可是正序收集就不是这样了
先是个位
37 47 48 38
然后就是十位
38 37 48 47
然后就乱了 所以这就是倒序收集的精髓