基数排序
标签: 数据结构
学习人数: 12.8k

前言

基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

 

算法思想

基本思想:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

算法步骤:

基数排序的方式可以采用 LSD(Least significant digital)或 MSD(Most significant digital),LSD 的排序方式由键值的最右边开始,而 MSD 则相反,由键值的最左边开始。

不妨通过一个具体的实例来展示一下基数排序是如何进行的。 设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。

我们知道,任何一个阿拉伯数,它的各个位数上的基数都是以 0~9 来表示的,所以我们不妨把 0~9 视为 10 个桶。

我们先根据序列的个位数的数字来进行分类,将其分到指定的桶中。例如:R[0] = 50,个位数上是 0,将这个数存入编号为 0 的桶中。

排序(8):基数排序

分类后,我们在从各个桶中,将这些数按照从编号 0 到编号 9 的顺序依次将所有数取出来。这时,得到的序列就是个位数上呈递增趋势的序列。

按照个位数排序: {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。

接下来,可以对十位数、百位数也按照这种方法进行排序,最后就能得到排序完成的序列。

动态效果示意图:

排序(8):基数排序

代码实现

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;
int a[maxn];
/*思想:基数排序其实就是按位排序、实现时用分桶的方法
可以从低位到高位、也可以从高位到低位*/
void Radix_Sort(int n, int k) {
    vector<int> v[10];//10个位对应10个桶
    int radix = pow(10, k);
    int flag = 1;
    for (int i = 1; i <= n; i++) {
        if (a[i] >= radix) flag = 0;
        int w = (a[i] % radix) / (radix / 10);
        v[w].push_back(a[i]);
    }
    int cnt = 1;
    for (int i = 0; i <= 9; i++) {//从低到高枚举每个位
        for (int j = 0; j < v[i].size(); j++) {
            a[cnt++] = v[i][j];
        }
    }
    if (flag) return;
...
登录查看完整内容


课后作业

课后习题

 

【2013年真题】对给定的关键字序列 110,119,007,911,114,120,122 进行基数排序,则第 2 趟分配收集后得到的关键字序列是 
A.007,110,119,114,911,120,122         
B.007,110,119,114,911,122,120 
C.007,110,911,114,119,120,122         
D. 110,120,911,122,114,007,119 

参考答案:C
答案解析:基数排序的第 1 趟排序是按照个位数字来排序的,第 2 趟排序是按然十位数字的大小进行排序的,答案是 C 选项。 


登录后开始许愿

暂无评论,来抢沙发