基数排序

in 数据结构 with 1 comment

之前讨论的排序均是通过比较来实现的,而基数排序(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;
}

动图演示:

9kb7DxUg8E.gif

注:图片来自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)

稳定性:

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

复杂性:

较复杂

归位:

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

Responses
  1. study 一起学习 go

    Reply