排序算法 - 基数排序(Radix Sort)

by LauCyun Aug 13,2014 22:22:20 6,924 views

基数排序 (Radix Sort) 是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。基数排序的发明可以追溯到 1887 年赫尔曼·何乐礼打孔卡片制表机 (Tabulation Machine)上的贡献。

基数排序法会使用到桶 (Bucket),顾名思义,通过将要比较的位(个位、十位、百位…),将要排序的元素分配至 0~9 个桶中,借以达到排序的作用,在某些时候,基数排序法的效率高于其它的比较性排序法。

所以,排序过程如下:

  • 分配:先从个位开始,根据位值(0-9)分别放到0~9号桶中(比如53,个位为3,则放入3号桶中);
  • 收集:再将放置在0~9号桶中的数据按顺序放到数组中;
  • 重复上面的过程,从个位到最高位,直到排好序为止(比如32位无符号整形最大数4294967296,最高位10位)。

 

1 实例分析

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

以LSD为例,假设有10个数的输入数组如下所示:

[73, 22, 93, 43, 55, 14, 28, 65, 39, 81]

首先根据个位数的数值,在走访数值时将它们分配至编号0到9的桶子中:

0 1 2 3 4 5 6 7 8 9
- 81 22 73 14 55 - - 28 39
      93   65        
      43            

接下来将这些桶子中的数值重新串接起来,成为以下的数列:

[81, 22, 73, 93, 43, 14, 55, 65, 28, 39]

接着再进行一次分配,这次是根据十位数来分配:

0 1 2 3 4 5 6 7 8 9
- 14 22 39 43 55 65 73 81 93
    28              

接下来将这些桶子中的数值重新串接起来,成为以下的数列:

[14, 22, 28, 39, 43, 55, 65, 73, 81, 93]

这时候整个数列已经排序完毕;如果排序的对象有三位数以上,则持续进行以上的动作直至最高位数为止。 

LSD的基数排序适用于位数小的数列,如果位数多的话,使用MSD的效率会比较好,MSD的方式恰与LSD相反,是由高位数为基底开始进行分配,其他的演 算方式则都相同。 

 

2 算法实现

C

 #include <stdio.h>
#include <stdlib.h>

#define N 10              // 数组个数
#define BUCKETS_NUM 10    // 桶个数

void Show(const int *arr, const int n);

int GetNumInPos(int num, int pos);

void Show(const int *arr, const int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%-4d", arr[i]);
    printf("\n");
}


int GetNumInPos(int num, int pos) {
    int temp = 1;
    for (int i = 0; i < pos - 1; i++)
        temp *= 10;

    return (num / temp) % 10;
}


void RadixSort(int *parray, const int n, const int k) {
    /// 分别为0~9的序列空间
    int *buckets[BUCKETS_NUM];
    for (int i = 0; i < 10; i++) {
        buckets[i] = (int *) malloc(sizeof(int) * (n + 1));
        buckets[i][0] = 0;    // index为0处记录这组数据的个数
    }

    for (int pos = 1; pos <= k; pos++) {
        // 分配过程
        for (int i = 0; i < n; i++) {
            int num = GetNumInPos(parray[i], pos);
            int index = ++buckets[num][0];
            buckets[num][index] = parray[i];
        }

        for (int i = 0, j = 0; i < BUCKETS_NUM; i++) {
            for (int k = 1; k <= buckets[i][0]; k++)
                parray[j++] = buckets[i][k];
            buckets[i][0] = 0;    //复位
        }
    }
}


int main() {
    int array[N] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81};

    printf("before sorting:\n");
    Show(array, N);

    RadixSort(array, N, 2);

    printf("after sorting:\n");
    Show(array, N);

    return 0;
}

Python

 #!/usr/bin/env python
# -*- coding: utf-8 -*-


def radix_sort(lst, k):
    for k in range(d):  # 排序轮数
        buckets = [[] for i in range(10)]  # 因为每一位数字都是0~9,故建立10个桶

        """
        对于数组中的元素,首先按照最低有效数字进行排序,然后由低位向高位进行。
        """
        for i in lst:
            """
            对于3个元素的数组[977,87,960]:
            第一轮排序首先按照个位数字相同的放在一个桶:s[7]=[977],s[7]=[977,87],s[0]=[960],执行后list=[960,977,87]
            第二轮按照十位数:s[6]=[960],s[7]=[977],s[8]=[87],执行后list=[960,977,87]
            第三轮按照百位:s[9]=[960],s[9]=[960,977],s[0]=87,执行后list=[87,960,977],结束。
            """
            index = int(i / (10 ** k) % 10)  # 73/10=7(小数舍去), 73/100=0
            buckets[index].append(i)
        lst = [j for i in buckets for j in i]
    return lst


unsorted_list = [73, 22, 93, 43, 55, 14, 28, 65, 39, 81]
print(radix_sort(unsorted_list, 2))

 

3 复杂度分析

基数排序的时间复杂度是\({\displaystyle O(k\cdot n)}\),其中\({\displaystyle n}\)是排序元素个数,\({\displaystyle k}\)是数字位数。注意这不是说这个时间复杂度一定优于\({\displaystyle O\left(n\cdot \log \left(n\right)\right)}\)\({\displaystyle k}\)的大小取决于数字位的选择(比如比特位数),和待排序数据所属数据类型的全集的大小;\({\displaystyle k}\)决定了进行多少轮处理,而\({\displaystyle n}\)是每轮处理的操作数目。

以排序\({\displaystyle n}\)个不同整数来举例,假定这些整数以\({\displaystyle B}\)为底,这样每位数都有\({\displaystyle B}\)个不同的数字,\({\displaystyle k=\log _{B}N}\)\({\displaystyle N}\)是待排序数据类型全集的势。虽然有\({\displaystyle B}\)个不同的数字,需要\({\displaystyle B}\)个不同的桶,但在每一轮处理中,判断每个待排序数据项只需要一次计算确定对应数位的值,因此在每一轮处理的时候都需要平均\({\displaystyle n}\)次操作来把整数放到合适的桶中去,所以就有:

\({\displaystyle k\approx \log _{B}N}\)

所以,基数排序的平均时间\({\displaystyle T}\)就是:

\({\displaystyle T\approx \log _{B}\left(N\right)\cdot n}\)

其中前一项是一个与输入数据无关的常数,当然该项不一定小于\({\displaystyle \log n}\)

如果考虑和比较排序进行对照,基数排序的形式复杂度虽然不一定更小,但由于不进行比较,因此其基本操作的代价较小,而且在适当选择的\({\displaystyle B}\)之下,\({\displaystyle k}\)一般不大于\({\displaystyle \log n}\),所以基数排序一般要快过基于比较的排序,比如快速排序。

 

4 参考文档

(全文完)

Tags