7.9 基数排序

    2.1基数排序图文说明

    通过基数排序对数组{53, 3, 542, 748, 14, 214, 154, 63, 616}，它的示意图如下：

    在上图中，首先将所有待比较树脂统一为统一位数长度，接着从最低位开始，依次进行排序。

    1. 按照个位数进行排序。
    2. 按照十位数进行排序。

    排序后，数列就变成了一个有序序列。

    2.2基数排序代码

    radix_sort(a, n)的作用是对数组a进行排序。

    2. 获取到数组a中的最大指数之后，再从指数1开始，根据位数对数组a中的元素进行排序。排序的时候采用了桶排序。

    3. count_sort(a, n, exp)的作用是对数组a按照指数exp进行排序。 下面简单介绍一下对数组{53, 3, 542, 748, 14, 214, 154, 63, 616}按个位数进行排序的流程。

      1. 个位的数值范围是[0,10)。因此，参见桶数组buckets[]，将数组按照个位数值添加到桶中。

        img

      2. 接着是根据桶数组buckets[]来进行排序。假设将排序后的数组存在output[]中；找出output[]和buckets[]之间的联系就可以对数据进行排序了。

    3.1基数排序C实现

    实现代码(radix_sort.c)

    3.2基数排序C++实现

    实现代码(RadixSort.cpp)

    3.3基数排序Java实现

    实现代码(RadixSort.java)

    上面3种实现的原理和输出结果都是一样的。下面是它们的输出结果：