经典排序之——基数排序

· · 算法·理论

算法原理

基数排序(Radix Sort)， 和桶排序、计数排序比较类似，都用到了“桶”的思想，基数排序将每个元素按位切割成不同的数字(也可以是字符)，对这些数字进行排序。具体步骤如下：

  1. 我们找出待排序列当中的最大元素，并求出它的位数。

  2. 从低位(MSD基数排序)或者从高位(LSD基数排序)开始，将所有数的同一位放入桶中，并通过其他算法(往往是计数算法)进行排序。

  3. 沿着数位重复操作2 。

时间复杂度

基数排序的时间复杂度为：O(d*(n+k))，其中n为元素个数，d为元素位数，k为元素范围

算法稳定性

稳定性的定义：在排序算法中如果该算法保证了两个相等的元素在排序后的序列中的相对位置和它们在原始序列中的相对位置相同，那么我们就称这个排序算法是稳定的。

上述中我们可以看出，由于基数排序需要分离出位数进行排序，对稳定性有非常严格的要求，所以是一种稳定的排序算法。

算法示意图


注：图片来自菜鸟教程

代码实现

#include<iostream>
#include<cstdlib>
#include<time.h>
#include<vector>
using namespace std;

int N = 30;
vector <int> a;

int getMax(vector<int>& x) 
{
    int max_num = x[0];
    for (unsigned int i = 1; i < x.size(); i++) 
        max_num = max(max_num,x[i]);
    return max_num;
}

void countSort(vector<int>& x, int exp) 
{
    vector<int> output(x.size());
    vector<int> count(10, 0);

    for (unsigned int i = 0; i < x.size(); i++) 
        count[(x[i] / exp) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = x.size() - 1; i >= 0; i--) 
    {
        output[count[(x[i] / exp) % 10] - 1] = x[i];
        count[(x[i] / exp) % 10]--;
    }

    for (unsigned int i = 0; i < x.size(); i++)
        x[i] = output[i];
}

void radixSort(vector<int>& x) 
{
    int max_num = getMax(x);

    for (int exp = 1; max_num / exp > 0; exp *= 10) 
        countSort(x, exp);
}

int main() 
{
    srand((unsigned)time(NULL));
    cout << "The original sequence is:";
    for (int i = 0; i < N; ++i) 
    {
        a.push_back(rand() % 100);
        cout << a[i] << " ";
    } 
    cout << endl; // 随机生成序列

    radixSort(a);

    cout << "The sorted sequence is:";
    for (int i = 0; i < N; ++i)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

代码解析

  1. 首先我们定义了一个函数int getMax(vector<int>& x) 用于寻找待排序列中最大元素。

  2. 我们通过计数排序void countSort(vector<int>& x, int exp) 对待排序列元素的每一位进行排序，其中 x 表示待排序列，exp 表示指数，即当exp=1时，我们是排序的个位，当exp=10时，我们是排序的十位。

  3. 在countSort 中output 数组是用于暂时存放输出的数组，count是用于记录每个位数出现次数的数组。我们首先通过count[(x[i] / exp) % 10]++; 求出每一位出现的次数，然后求一个前缀和：count[i] += count[i - 1]; ，使用前缀和的目的是为了防止数字被覆盖，如果还是不太理解可以继续往下看。

  4. 我们通过output[count[(x[i] / exp) % 10] - 1] = x[i]; 将待排数组的每一个数字填进 output 数组中，(x[i] / exp) % 10用于提取该数的对应数位，减一是因为数组索引从0开始的。这时候前缀和的公用就发挥出来了，每一个数位都为前面的的数位预留了位置。
    举个例子：
    如果我们的数位'1'有2个，'3'有1个，'4'有2个，'6'有2个，'9'有1个，那我们的 count 数组应该长这样:
    数位 0 1 2 3 4 5 6 7 8 9
    数组 0 2 2 3 5 5 7 7 7 8
    我们不难看出当我们在把该数位为'4'的数填进去时，由于前缀和加上了比它小的位数，所以我们会把它填入索引为3或4(别忘了数组从0开始要减一)的地方，为前面数位'1'数位'3'留出了空间，保证了output的有序。

  5. 函数的最后我们把output中的元素重新覆盖原数组即可。

  6. 在函数void radixSort(vector<int>& x) 中，我们通过这个函数来逐一确定排序的位次，到底是个位还是十位还是百位。exp从1开始，逐渐扩大十倍，每一次扩大都代表数位升高一位，上升到最和最大的数字位数相同时就停止。

算法优点

算法缺点

宇宙安全声明

人难免疏忽，如果文章中有错误或其他不妥的言语措辞，欢迎大家友善指正。