LSDhttps://blog.csdn.net/qq845579063/article/details/51447772
MSDhttps://blog.csdn.net/u011948899/article/details/78027838
自己写的LSD模板 vector实现
解析
注释挺详细的，基本还原了上述博客的思想（模拟）
#include<cstdio>//基排序 不支持负数，如果有负数，请加上一定的数使得他们全为正 或者基数翻倍，把负数也算作基数
#include<iostream>//思想https://blog.csdn.net/qq845579063/article/details/51447772
#include<vector>
#include<algorithm>
using namespace std;
int maxbit(int data[],int n) { //获取数组数据最大位数，n为数组下标上界（从0开始）
int m=-1;
for(int i=0; i<=n; i++) { //获取数组绝对值最大值
m=max(m,data[i]);
}
int p=0;
while(m>0) {
m/=10;
p+=1;//m==451 进入循环,m=45,p=1;m==45进入循环,m=4,p=2;m==4进入循环,m=0,p=3;m==0退出循环
}
return p;
}
void rsortUp(int data[],int n,int r) { // ***由小到大递增版 低位优先LSD版***r为基数 比如10 n为数组最后一个元素下标,从0开始
int b=maxbit(data,n); //时间复杂度O(bn) b为最大位数
int radix[100]= {0};
radix[1]=1;//基数数组
for(int i=2; i<=b; i++) { //预处理基数数组 时间复杂度O(bn)
radix[i]=radix[i-1]*r;
}
for(int i=1; i<=b; i++) { //每一位的排序 外层循环b次 整体时间复杂度O(bn)
vector <int> temp[200];//每一位排序后的桶的过渡数组 存放桶中的元素
for(int j=0; j<=n; j++) { //遍历数组的每个数 放入对应桶中 时间复杂度O(n)
int k=(data[j]/radix[i])%10;//获取第b位的数
temp[k].push_back(data[j]);
}
int cnt=-1;//data的临时计数器
for(int l=0; l<=r-1; l++) { //把temp中的数重新放回data中 l为位数 时间复杂度O(n)
for(int q=0; q<temp[l].size(); q++) { //q为每个桶的数序号
data[++cnt]=temp[l][q];
}
}
}
}
void rsortDown(int data[],int n,int r) { // ***由小到大递减版 低位优先LSD版***
int b=maxbit(data,n);
int radix[100]= {0};
radix[1]=1;
for(int i=2; i<=b; i++) {
radix[i]=radix[i-1]*r;
}
for(int i=1; i<=b; i++) {
vector <int> temp[200];
for(int j=0; j<=n; j++) {
int k=(data[j]/radix[i])%10;
temp[k].push_back(data[j]);
}
int cnt=-1;
for(int l=r-1; l>=0; l--) { //*******这里与Up不一样
for(int q=0; q<temp[l].size(); q++) {//*****这里与Up不一样 其他的都一样哦
data[++cnt]=temp[l][q];
}
}
}
}
int main() {
int arr[] = { 47,54,18,678,23,489,135,7498,46,14,2,3};
int len = (int) sizeof(arr) / sizeof(*arr);
rsortUpMSD(arr,len-1,10);
for(int i=0; i<len; i++) cout<<arr[i]<<" ";
return 0;
}网上的LSD模板 数组实现
解析
递增递减关键在于count，注释上解释了如何改变递增递减
大家可以先看一下模板，其他地方跟我自己写的模板差不多，注释详细，不懂的请在评论区留言。
然后我重点讲解两句话
第一句
tmp[count[k] - 1] = data[j];问题：为什么要这么做?
第二句
for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中 注意j是从n-1开始倒序遍历这两句话属于一个模块
for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中 注意j是从n-1开始倒序遍历
{
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];//https://mp.csdn.net/mp_blog/creation/editor/119847991见解析
count[k]--;
}问题：为什么j要从后往前遍历？?
本着理解循环要从内往外的原则，我们先讲问题1，再讲问题2
问题1
这句话我研究了两天才看懂
?
?由于处理了前缀和：
for(j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; //计算count前缀和 因此对每一位位数k而言，count[k]的下标都可以对应到temp中去。
你可能会疑惑：我记录count的时候并没有把data的数据存入count中，count是怎么知道哪一位存放的是什么元素呢？其实你让count[k]++的时候，遍历数组是按一定顺序的。第一次遍历就是原数组的顺序，第二次遍历是第一次排序后的顺序，以此类推，而一旦遍历顺序确定，再给你下标，你难道无法得知这个数据么？知二求一，显然可以。所以我们不需要把具体数据加进去。
而count是从1开始计数的，所以count[k]-1是从0开始，减1就是为了让temp从0开始计数
temp与count的对应关系正如上图蓝笔标注一样，蓝笔标的是temp的下标，以第一次模拟来说，count[1]=1，count[2]=3，count[4]=4,count[5]=5,……，而count的每一位下标对应的元素也如图所示，正如上面解析所言，加入count的逻辑顺序确定，下标确定，具体元素自然确定。
tmp[count[k] - 1] = data[j];加入的逻辑顺序就是data[j]，下标就是count[k]-1,那么，tmp数组顺理成章地构建完毕
之后再把tmp赋值给data就行了，一次迭代完成
问题2
因为我们把data[]数组存放到count[]数组的顺序是从前往后放的，如果取出count[]的数据的顺序也是从前往后，那么就会导致小数先被取出，大数后被取出（这里的大小是上一轮排序后得到的相对大小，在第一轮两种取法没区别，第二轮起区别很大）。每次取数会导致count--,因此后取出来的大数实际上在tmp[]中是排在小数前面的，即后发先至。正常顺序是小数排在大数前面！因此，我们让count[]的小数后被取出排在tmp[]前面的位置，大数先被取出排在靠后的位置。
模板
#include <iostream>
using namespace std;
void printArray(int array[],int length)//打印数组
{
for (int i = 0; i < length; ++i)
{
cout << array[i] << " ";
}
cout << endl;
}
int maxbit(int data[], int n) //求数据的最大位数,决定排序次数
{
int d = 1; //保存最大的位数
int p = 10;
for(int i = 0; i < n; ++i)
{
while(data[i] >= p)
{
p *= 10;
++d;
}
}
return d;
}
void radixsort(int data[], int n) //基数排序 *****41~42行为递增版 43~44行为递减版******
{
int d = maxbit(data, n);
int tmp[n];
int count[10]; //计数器
int i, j, k;
int radix = 1;
for(i = 1; i <= d; i++) //进行d次排序
{
for(j = 0; j < 10; j++)
count[j] = 0; //每次分配前清空计数器
for(j = 0; j < n; j++)
{
k = (data[j] / radix) % 10; //统计每个桶中的记录数
count[k]++;
}
for(j = 1; j < 10; j++) //***递增版
count[j] = count[j - 1] + count[j]; //计算count前缀和 //***递增版
// for(j=8;j>=0;j--) //***递减版
// count[j]+=count[j+1]; //***递减版
for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中 注意j是从n-1开始倒序遍历
{
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];//https://mp.csdn.net/mp_blog/creation/editor/119847991见解析
count[k]--;
}
for(j = 0; j < n; j++) //将临时数组的内容复制到data中
data[j] = tmp[j];
radix = radix * 10;
// cout<<"d="<<i<<"时 tmp数组:";printArray(tmp,n) ;
}
}
int main()
{
int array[5] = {6,101,24,35,32};
radixsort(array,5);
printArray(array,5);
return 0;
}