【数据结构】基数排序高位优先(MSDF)

基数排序常用写法是低位优先(LSD),在网上有很多,还有一种写法是高位优先排序(MSDF)

高位优先资料比较少,而且老师布置了一个高位优先的题目,所以也尝试了高位优先的写法,下面来说说吧,程序可以实现功能,但未必完美,期待大佬给出改进的建议????

高位优先基数排序的基本思路

  1. 确定基数:基数排序通常使用基数为 10,因为十进制数字的范围是从 0 到 9。
  2. 逐位排序:从最高位开始逐位进行排序,直到最低位。
  3. 使用桶排序:每一轮排序都使用桶排序(bucket sort)的思想,将数字按照当前位的值放入对应的桶中。
  4. 递归排序:对于每个桶中的元素,继续递归地进行基数排序。

图解算法

基数排序高位优先的思想是递归+分治

①确定最大值:8788,有4位,因为是高位优先,可以通过这样确定先比较千位上的数

②遍历数组,将每个数字放入对应其千位的数字的桶中

③第一趟排序之后, 在千位上已经有序了,遍历每个桶,如果这个桶中有数字,而且只有一个数字(只有一个数字时认为就是有序的),那么可以收集它了,0389,2375。

④收集到3号桶时,我们发现有好几个千位是3的,而且并不是有序的,那么这个桶还要继续排序,千位相同,那就比较百位,它的策略跟第一趟排序相同,这里就用到了递归

 

⑤第二趟排序之后,3号桶中的数字变得有序了,按照0~9遍历第二趟排序的桶,收集数字,那么第一层函数中的3号桶中的数字收集完毕,递归结束。

⑥继续遍历,第一层函数中的4号桶中不止一个元素,需要排序

⑦遍历递归后的桶中元素,并收集,发现8号桶中不止一个元素,对它进行递归

⑧4873,4871仍然未排好序,继续递归

经历这次递归,4873,4871已经有序,收集号元素后返回上一层递归,上一层递归继续返回,直到返回第一层函数中

递归的结束条件:

如果桶中只有一个元素,可以认为有序,递归结束,或者,已经比较完所有位数,即千位,百位,十位,个位都比较完,递归也结束

Code

主函数

int main()
{

    vector<int>a={4873,4871,6248,2375,3320,5523,3246,8788,389,4573,389};
    int max_num=a[0];
    for(int i=1;i<a.size();i++)
    {
        max_num=max_num>a[i]?max_num:a[i];//找到最大值,知道有多少位
    }
    int num=to_string(max_num).size();//获取最大值的位数
    Radix_Sort_rec(a,int(pow(10,num)));//递归基数排序

    for(int i=0;i<temp.size();i++)cout<<temp[i]<<' ';//输出排序后的数组
    cout<<endl;
    return 0;
}

 基数排序

void Radix_Sort_rec(vector<int>a,int n)
{
    vector<vector<int>>bulb(10);//初始化10个桶,用来装数字(0~9)
    for(int i=0;i<a.size();i++)
    {
        bulb[a[i]/n%10].push_back(a[i]);//将对应位数的数字放入对应桶中
    }
    for(int i=0;i<10;i++)
    {
        if(bulb[i].size()){
            if(bulb[i].size()==1||n<10)Merge(bulb[i]);//递归结束,收集元素
            else Radix_Sort_rec(bulb[i],n/10);
        }
    }
}

收集元素

vector<int>temp;
void Merge(vector<int>num)
{
    for(int i=0;i<num.size();i++)temp.push_back(num[i]);
}

完整代码

#include<bits/stdc++.h>

using namespace std;
/*
 实现MSDF(高位优先)算法给正整数排序
 注:正整数的输入可以设置诸如以下二维数组这种形式(也可自己根据自己的习惯*设定):
 int A[NUM][RADIX] = {{4,8,7,3},{4,8,7,1},{6,2,4,8},{2,3,7,5},{3,3,2,0},{5,5,2,3},{3,2,4,6},
 {8,7,8,8},{0,3,8,9},{4,5,7,3}};//对4873、4871、6248等整数进行排序
 */
vector<int>temp;
void Merge(vector<int>num)
{
    for(int i=0;i<num.size();i++)temp.push_back(num[i]);
}
void Radix_Sort_rec(vector<int>a,int n)
{
    vector<vector<int>>bulb(10);//初始化10个桶,用来装数字(0~9)
    for(int i=0;i<a.size();i++)
    {
        bulb[a[i]/n%10].push_back(a[i]);//将对应位数的数字放入对应桶中
    }
    for(int i=0;i<10;i++)
    {
        if(bulb[i].size()){
            if(bulb[i].size()==1||n<10)Merge(bulb[i]);//递归结束,收集元素
            else Radix_Sort_rec(bulb[i],n/10);
        }
    }
}
int main()
{

    vector<int>a={4873,4871,6248,2375,3320,5523,3246,8788,389,4573,389};
    int max_num=a[0];
    for(int i=1;i<a.size();i++)
    {
        max_num=max_num>a[i]?max_num:a[i];//找到最大值,知道有多少位
    }
    int num=to_string(max_num).size();//获取最大值的位数
    Radix_Sort_rec(a,int(pow(10,num)));//递归基数排序

    for(int i=0;i<temp.size();i++)cout<<temp[i]<<' ';//输出排序后的数组
    cout<<endl;
    return 0;
}

 

上一篇:【MATLAB】TOA/TDOA测距定位,三维任意(>3)个锚节点,对一个未知点进行定位-引言


下一篇:JVM 类加载机制