基数排序 - ONESRC

数据结构排序分配收集

之前讨论的排序均是通过比较来实现的，而基数排序（Radix sort）是一种非比较型整数排序算法，它通过“分配”和“收集”来实现排序。

1.排序思路

基本分析

一般情况下，元素R[i]由d位的数字（或者字符）组成

$$ k^{d-1}k^{d-2}...k^{1}k^{0} \quad and \quad 0\leq k^i \lt r \quad $$

其中$k^{d-1}$为最高位，$k^{0}$为最低位，r称为基数（radix）

例如二进制基数为2，十进制基数为10

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

分配和收集

排序过程中需要使用r个队列，为方便理解，我们将其记为Q[0..r-1]

以LSD为例，整个排序过程实际上就是对i=0,1...,d-1,依次做一次分配和收集

分配：开始时,把各个队列置空，依次考察每一个元素$a_j(j=0,1,...d-1)$，如果元素的$k_j^i=k$，把元素$a_j$插入到队列Q[k]中。即若第j个元素的第i位对应的值k，则它被放到队列Q[k]中。（稳定性）

收集：将Q[0..r-1]各个队列依次首尾相连，得到新的元素序列。

以int为例

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

2.排序算法

以c为例,从小到大排序，采用LSD。

#include <stdio.h>

void radix_sort(int R[], int n){
    int i, tmp[n], maxVal = 0, digit;
    for (i = 0; i < n; i++){//寻找最大元素
        if (R[i] > maxVal)maxVal = R[i];
    }
    for (digit = 1; maxVal / digit > 0;digit*= 10){//LSD,从最低位开始，循环至最高位
        int count[10] = {}; //10个单位分别对应于10个队列
        for (i = 0; i < n; i++){//分配
            count[R[i] / digit % 10]++; //R[i] / digit % 10获得的是一次循环中，该元素对应的队列
        }
        for (i = 1; i < 10; i++){//首尾连接
            count[i] += count[i - 1];
        }
        for (i = n - 1; i >= 0; i--){//放入tmp后，首尾连接完成。
            tmp[--count[R[i] / digit % 10]] = R[i];
        }
        for (i = 0; i < n; i++){//放回。链表结构存储时，无此操作。下面的复杂度分析忽略此处。
            R[i] = tmp[i];
        }
        //打印一次分配收集后的结果
        printf("%d:" ,digit);
        for (i = 0; i < n; i++){
            printf("%d ", R[i]);
        }
        printf("\n");
    } 
}

int  main(void){
    int a[] = {75,23,98,44,57,12,29,64,38,82};
    radix_sort(a, 10);
    return 0;
}

动图演示：

注：图片来自https://visualgo.net

输出结果：

1:12 82 23 44 64 75 57 98 38 29 //对个位进行分配收集
10:12 23 29 38 44 57 64 75 82 98//对十位进行分配收集

注：上述函数不适用于负数情况，对于存在负数的排序，可以按正负分别排序，最后合并在一起，此处不再单独给出具体算法。

3.算法分析

时间复杂度：

共进行d趟分配和收集，一次分配时间为O(n)，一次收集为O(r)，所以总的时间复杂度为O(d(n+r))

空间复杂度：

需要创建r个队列，空间复杂度为O(r)

稳定性：

分配过程有先后顺序，这是一种稳定的排序方法。

复杂性：

较复杂

归位：

否，基数排序不产生有序区

本文由 ukuq 创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Feb 2, 2019 at 07:55 pm