DSA之十大排序算法第十种：Radix Sort
2023-09-14 09:15:35 时间
基数排序 2019年9月2日14:31:03
建议：在看本篇博客时：请先回顾DSA之十大排序算法第八种：Counting Sort 和 DSA之十大排序算法第九种：Bucket Sort 。
基数排序 vs 计数排序 vs 桶排序的对比如下：
- 这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
- Radix Sort：根据键值的每位数字来分配桶；
- Counting Sort：每个桶只存储单一键值；
- Bucket Sort ：每个桶存储一定范围的数值；
基数排序同样也是一种非比较型的排序算法，其基本思想：将数据元素按 位数 切割成不同的数字，然后按每个 位数 分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
由于排序顺序的不同，通常将基数排序分为LSD（Least Significant Digital）或 MSD（Most Significant Digital）两种方式。LSD的排序方式由数值的最右边（低位）开始；而MSD则不同，是由数值的最左边（高位）开始。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配之后，再将全部数据合并回原来的数组之中。
注：LSD的基数排序适用于数据元素位数少的数列，若位数比较多的情况下，使用MSD的效率会比较好一点。既然是类“桶排序”，这里的桶的数目就是10了，分别对应关键码 0 1 2 3 4 5 6 7 8 9 。
排序步骤就是：（这里以LSD为例）
- 根据最低位关键码Kd对所有数据元素进行一趟排序，每个数据元素由其个位的值 决定其在哪个桶里面放置。
- 个位数排序放置完毕之后，从0号桶开始，依次将每个桶里面的数据元素 汇集起来。然后再依据次低位关键码Kd-1（十位）对上一趟排序的结果再排序。
- 依次重复步骤1 2，直到依据关键码K1（最高位） 也即最后一趟排序完成，就可以得到一个有序的序列。
- 使用这种排序方法LSD 对每一个关键码（从低位到高位）进行排序时，不需要再分组，而是针对整个数组再次进行操作。
| 分析具体实现（LSD）： |
如上图所示（从菜鸟网站“拿”来的）：面对下面的一组数据：
123,234,564,765,876,324,651,874,432
十个桶：分别对应关键码 0 1 2 3 4 5 6 7 8 9
5. 从头到尾遍历将要排序的序列，找出数值最大的数据元素maxval(目的是：为了得到这个数列中最大的数maxval是几位数，以便进行几次的循环操作)。
6. 临时开辟一个与原无序数组大小相同的临时temp_src，来存放每一个低位一次排序后的中间结果。
7. 接下来就是把数据读入到 对应的桶里面。如下代码所示：
if (i == 0)//就是说：第一次读所有数据的时候 是从src来的
{
for (int val : src)
{
int num = Get_thisBit_num(val, thisbit);//得到该位数字
myBucket[num].push_back(val);//放入对应的桶里面
}
}
else//此后读的就是临时数组里面的数据元素了
{
for (int val : temp_src)
{
int num = Get_thisBit_num(val, thisbit);
myBucket[num].push_back(val);//放入桶里面
}
temp_src.clear();//读完了之后 temp_src数组也得清空
}
- 接下来如下：遍历每一个桶，把数据放入到temp_src里面（注意顺序）
//每个数字 放入桶里面之后，接下来就需要把每个桶里面的数据依次放入到
//temp_src里面了
//但是temp_src里面的 仍旧是无序的中间结果而已
for (int i = 0; i < Bucket_Num; ++i)
{
vector<int>::iterator it = myBucket[i].begin();
while (it != myBucket[i].end())
{
temp_src.push_back(*it);
it++;
}
myBucket[i].clear();//该号桶 下次还要用呢
}
- thisbit *= 10;//到下一位了 继续循环，不过下次桶就是从临时数组temp_src里面 读入的数据了。重复操作，直到Bit_of_maxval次数到达为止。
- 最后把数据 写入到src里面即可，如下：
src.clear();
//排序结束了，temp_src数据得给src了
for (int val : temp_src)
{
src.push_back(val);
}
| 分析具体算法（LSD）： |
- 基数排序是通过“分配”和“收集”两个步骤来完成排序。首先根据每个数据个位数的数值，在遍历数据时将它们各自分配到编号0至9的桶（个位数值与桶号一一对应）中。分配结束后。接下来将所有桶中（由顶至底）所盛数据按照桶号由小到大依次重新收集串起来，得到仍然无序的数据序列存放在temp_src里面。接着，再进行一次分配，这次根据每个数据十位数的数值来分配（原理依旧）。分配结束后。接下来再将所有桶中（由顶至底）所盛的数据（原理依旧）依次重新再收集串接起来，得到最终的数据序列存放在temp_src里面，但是已然有序了。
- 基数排序也是 稳定的排序算法。如下：一组数据：10 12 31 24 12，暂且称左边的12为先12，右边的12为后12.
一次排序如下（按照LSD，从个位开始）：
收集数据，再行处理之前：
接下来按照 十位进行排序：
于是最终结果：
| 算法测试打印（LSD）： |
const int Bucket_Num = 10;//这里当然是10个桶
/*
123
123 / 1 % 10 == 3
123 / 10 % 10 == 2
123 / 100 % 10 == 1
*/
//得到这个thisbit位 上面的数字
int Get_thisBit_num(int data,int thisbit)
{
return data / thisbit % 10;
}
void Radix_Sort_LSD(vector<int>& src)
{
int size = src.size();
//先把桶空间给 开辟出来
vector<vector<int>>myBucket;
myBucket.resize(Bucket_Num);//10个桶
//得到这个数列里面最大的数据的位数 是几位
int maxval = src[0];
for (int i = 1; i < size; ++i)
{
if (src[i] > maxval)
maxval = src[i];
}
int Bit_of_maxval = 0;
while (maxval != 0)
{
Bit_of_maxval++;
maxval /= 10;
}
//得到了 位数就可以知道 要进行几次的排序操作了
//需要一个临时的temp_src来存放中间结果
vector<int>temp_src;
temp_src.reserve(size);
//接下来进行每一位的操作
//因为是LSD操作，从低位到高位
int thisbit = 1;//从个位开始
for (int i = 0; i < Bit_of_maxval ; ++i)//控制次数
{
if (i == 0)
{
for (int val : src)
{
int num = Get_thisBit_num(val, thisbit);
myBucket[num].push_back(val);//放入桶里面
}
}
else//此后读的就是临时数组里面的数据元素了
{
for (int val : temp_src)
{
int num = Get_thisBit_num(val, thisbit);
myBucket[num].push_back(val);//放入桶里面
}
temp_src.clear();//读完了之后 temp_src数组也得清空
}
//每个数字 放入桶里面之后，接下来就需要把每个桶里面的数据依
//次放入到temp_src里面了
//但是temp_src里面的 仍旧是无序的中间结果而已
for (int i = 0; i < Bucket_Num; ++i)
{
vector<int>::iterator it = myBucket[i].begin();
while (it != myBucket[i].end())
{
temp_src.push_back(*it);
it++;
}
myBucket[i].clear();//该号桶 下次还要用呢
}
thisbit *= 10;//到下一位了
}
src.clear();
//排序结束了，temp_src数据得给src了
for (int val : temp_src)
{
src.push_back(val);
}
}
| 算法测试打印（MSD）： |
极为重要 极为重要 极为重要 ！！！！
/**══════════════════════════════════╗
*作 者：songjinzhou ║
*CSND地址：https://blog.csdn.net/weixin_43949535 ║
***GitHub：https://github.com/TsinghuaLucky912/My_own_C-_study_and_blog║
*═══════════════════════════════════╣
*创建时间：2019年9月2日22:35:47
*功能描述：
*
*
*═══════════════════════════════════╣
*结束时间:
*═══════════════════════════════════╝
// .-~~~~~~~~~-._ _.-~~~~~~~~~-.
// __.' ~. .~ `.__
// .'// 西南\./联大 \\`.
// .'// | \\`.
// .'// .-~"""""""~~~~-._ | _,-~~~~"""""""~-. \\`.
// .'//.-" `-. | .-' "-.\\`.
// .'//______.============-.. \ | / ..-============.______\\`.
//.'______________________________\|/______________________________`.
*/
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
const int Bucket_Num = 10;//这里当然是10个桶
/*
123
123 / 1 % 10 == 3
123 / 10 % 10 == 2
123 / 100 % 10 == 1
*/
//得到这个thisbit位 上面的数字
int Get_thisBit_num(int data, int thisbit)
{
return data / thisbit % 10;
}
//递归实现版本
void Radix_Sort_MSD_Operator(vector<int>& this_bucket, vector<int>& temp_src, int this_bit)
{
if (this_bit == 0)
return;
//先把桶空间给 开辟出来
vector<vector<int>>myBucket;
myBucket.resize(Bucket_Num);//10个桶
//接下来就是 把*it 或者说 this_bucket里面的数据，从最后一个读入，
//MSD 最高位放入桶中
for (vector<int>::iterator it = this_bucket.end() - 1; it >= this_bucket.begin(); --it)
{
if (it == this_bucket.begin())
{
int num = Get_thisBit_num(*it, this_bit);
myBucket[num].push_back(*it);//放入桶里面
break;
}
int num = Get_thisBit_num(*it, this_bit);
myBucket[num].push_back(*it);//放入桶里面
}
for (vector<vector<int>>::iterator it = myBucket.begin();
it != myBucket.end(); ++it)
{
if ((*it).size() == 1)
{
for (int val : *it)
{
temp_src.push_back(val);
}
}
else if ((*it).size() > 1)
{
Radix_Sort_MSD_Operator(*it, temp_src, this_bit / 10);
for (int val : *it)
{
temp_src.push_back(val);
}
}
}
}
void Radix_Sort_MSD(vector<int>& src)
{
int size = src.size();
//先把桶空间给 开辟出来
vector<vector<int>>myBucket;
myBucket.resize(Bucket_Num);//10个桶
//得到这个数列里面最大的数据的位数 是几位
int maxval = src[0];
for (int i = 1; i < size; ++i)
{
if (src[i] > maxval)
maxval = src[i];
}
int Bit_of_maxval = 0;
while (maxval != 0)
{
Bit_of_maxval++;
maxval /= 10;
}
//得到了 位数就可以知道 要进行几次的递归排序操作了
//需要一个临时的temp_src来存放结果
vector<int>temp_src;
temp_src.reserve(size);
int this_bit = pow(10, Bit_of_maxval - 1);//3位数 就是100
//首先是 把src数据，从最后一个读入，MSD 最高位放入桶中
for (vector<int>::iterator it=src.end()-1;it>=src.begin();--it)
{
if (it == src.begin())
{
int num = Get_thisBit_num(*it, this_bit);
myBucket[num].push_back(*it);//放入桶里面
break;
}
int num = Get_thisBit_num(*it, this_bit);
myBucket[num].push_back(*it);//放入桶里面
}
for (vector<vector<int>>::iterator it = myBucket.begin();
it != myBucket.end(); ++it)
{
if ((*it).size() == 1)
{
for (int val : *it)
{
temp_src.push_back(val);
}
}
else if((*it).size() > 1)
{
Radix_Sort_MSD_Operator(*it, temp_src, this_bit / 10);
}
}
//排序结束了，temp_src数据得给src了
src.clear();
for (int val : temp_src)
{
src.push_back(val);
}
}
int main()
{
int Array[] = { 1,50,38,5,47,15,36,26,27,2,46,4,19,44,48 };
int Array2[] = { 9,21,32,13,34,45,26,37,8,10,26 };
int Array3[] = { 123,234,564,765,876,324,651,874,432,23,5,0 };
int Array4[] = { 19,19,21,34,16,78 };
vector<int>myvec(begin(Array), end(Array));
cout << "数列初始状态：";
for (int val : myvec)
cout << setw(2) << val << " ";
cout << endl;
cout << "/*------------------------------------*/" << endl;
Radix_Sort_MSD(myvec);
cout << "/*------------------------------------*/" << endl;
cout << "数列最终状态：";
for (int val : myvec)
cout << setw(2) << val << " ";
cout << endl
return 0;
}
/**
*备用注释：
*
*
*
*/
2019年9月2日23:58:39
终于把基于递归的MSD算法写出来了。非常重要！！！
相关文章
- 拓展欧几里德算法(exgcd)学习笔记
- 26·灵魂前端工程师养成-排序算法
- 排序算法总结
- 无监督学习的12个最重要的算法介绍及其用例总结（附链接）
- php 递归算法
- 十大经典排序算法详解(三)-堆排序,计数排序,桶排序,基数排序[通俗易懂]
- java实现四种常用排序算法
- 十大经典排序算法-快速排序算法详解
- 希尔排序，冷门但是有趣的排序算法
- 算法：第一章：SnowFlake算法（分布式系统中生成唯一的ID的算法）SnowFlake每秒能够产生26万ID左右
- 【数据结构与算法】：交换排序之快速排序（手绘图解+LeetCode原题）
- Java--十大排序算法
- 推荐系统[八]算法实践总结V2：排序学习框架(特征提取标签获取方式)以及京东推荐算法精排技术实战
- Go 数据结构和算法篇（十四）：哈希表、哈希函数、哈希冲突和哈希算法
- 混合高斯模型和EM算法
- 谈谈虚拟DOM，Diff算法与Key机制
- [Arxiv | 论文简读] 一种基于有符号图聚类的分布式多层模因算法
- 十大经典排序算法
- 安全帽识别算法技术原理
- 前端工程师leetcode算法面试必备-二分搜索算法（上）_2023-03-15
- python实现的堆排序算法代码详解编程语言
- 希尔排序算法的python实现详解编程语言
- 算法-删除链表中重复的结点详解编程语言
- C++ stable_sort(STL stable_sort)排序算法详解
- 新型算法横空出世，AI 大佬亲自为人工智能降火｜AI科技评论周刊
- 希尔排序的算法代码
- python算法学习之计数排序实例
- c++11新增的便利算法实例分析
- php实现的常见排序算法汇总