排序算法 - 基数排序

基本思想

基数排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶：O(n)。

实例

扑克牌中52张牌，可按花色和面值分成两个字段，其大小关系为：
花色： 梅花< 方块< 红心< 黑心
面值： 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A
若对扑克牌按花色、面值进行升序排序，得到如下序列：

即两张牌，若花色不同，不论面值怎样，花色低的那张牌小于花色高的，只有在同花色情况下，大小关系才由面值的大小确定。这就是多关键码排序。
为得到排序结果，我们讨论两种排序方法。
方法1：先对花色排序，将其分为4 个组，即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序，最后，将4 个组连接起来即可。
方法2：先按13 个面值给出13 个编号组(2 号，3 号，…，A 号)，将牌按面值依次放入对应的编号组，分成13 堆。再按花色给出4 个编号组(梅花、方块、红心、黑心)，将2号组中牌取出分别放入对应花色组，再将3 号组中牌取出分别放入对应花色组，……，这样，4 个花色组中均按面值有序，然后，将4 个花色组依次连接起来即可。
设n 个元素的待排序列包含d 个关键码{k1，k2，…，kd}，则称序列对关键码{k1，k2，…，kd}有序是指：对于序列中任两个记录r[i]和rj都满足下列有序关系：

其中k1 称为最主位关键码，kd 称为最次位关键码。

两种多关键码排序方法

多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序，分两种方法：

最高位优先(Most Significant Digit first)法，简称MSD 法：
1）先按k1 排序分组，将序列分成若干子序列，同一组序列的记录中，关键码k1 相等。
2）再对各组按k2 排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd 对各子组排序后。
3）再将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法。

最低位优先(Least Significant Digit first)法，简称LSD 法：
1) 先从kd 开始排序，再对kd-1进行排序，依次重复，直到按k1排序分组分成最小的子序列后。
2) 最后将各个子序列连接起来，便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。
基于LSD方法的链式基数排序的基本思想
　　“多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字，可以看作由多个数位或多个字符构成的多关键字，此时可以采用“分配-收集”的方法进行排序，这一过程称作基数排序法，其中每个数字或字符可能的取值个数称为基数。比如，扑克牌的花色基数为4，面值基数为13。在整理扑克牌时，既可以先按花色整理，也可以先按面值整理。按花色整理时，先按红、黑、方、花的顺序分成4摞（分配），再按此顺序再叠放在一起（收集），然后按面值的顺序分成13摞（分配），再按此顺序叠放在一起（收集），如此进行二次分配和收集即可将扑克牌排列有序。
基数排序:
是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

代码

package main.java.com.study.sortingAalgorithm;

import main.java.com.study.utils.CommonUtils;

/**
 * @author: whb
 * @description: 基数排序：过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。
 * 平均O(d(n+r)),最好O(d(n+r)),最坏O(d(n+r));空间复杂度O(n+r);稳定;较复杂
 * d为位数,r为分配后链表的个数
 */
public class RadixSort {

    /**
     * 基数排序
     *
     * @param unsorted 待排数组
     * @param max      最大几位数
     */
    public static void radixSort(int[] unsorted, int max) {
        //count数组用来计数
        int[] count = new int[unsorted.length];
        //bucket用来当桶，放数据，取数据
        int[] bucket = new int[unsorted.length];

        //k表示第几位，1代表个位，2代表十位，3代表百位
        for (int k = 1; k <= max; k++) {
            //把count置空，防止上次循环的数据影响
            for (int i = 0; i < unsorted.length; i++) {
                count[i] = 0;
            }

            //分别统计第k位是0,1,2,3,4,5,6,7,8,9的数量
            //以下便称为桶
            //即此循环用来统计每个桶中的数据的数量
            for (int i = 0; i < unsorted.length; i++) {
                count[getFigure(unsorted[i], k)]++;
            }

            //利用count[i]来确定放置数据的位置
            for (int i = 1; i < unsorted.length; i++) {
                count[i] = count[i] + count[i - 1];
            }
            //执行完此循环之后的count[i]就是第i个桶右边界的位置

            //利用循环把数据装入各个桶中，注意是从后往前装
            for (int i = unsorted.length - 1; i >= 0; i--) {
                int j = getFigure(unsorted[i], k);
                bucket[count[j] - 1] = unsorted[i];
                count[j]--;
            }

            //将桶中的数据取出来，赋值给unsorted
            for (int i = 0, j = 0; i < unsorted.length; i++, j++) {
                unsorted[i] = bucket[j];
            }
        }
    }

    /**
     * 返回整型数num的第pos位是什么
     *
     * @param num 整数num
     * @param pos pos=1表示个位，pos=2表示十位
     * @return
     */
    public static int getFigure(int num, int pos) {
        int tmp = 1;
        for (int i = 0; i < pos - 1; i++) {
            tmp *= 10;
        }
        return (num / tmp) % 10;
    }

    /**
     * 二维数组的方式实现基数排序
     *
     * @param unsorted 待排序列
     * @param arr_x    最大数字不超过999999999...(array_x个9)
     * @param arr_y    最大位数
     */
    public static void radix_sort(int[] unsorted, int arr_x, int arr_y) {
        for (int i = 0; i < arr_x; i++) {
            int[][] bucket = new int[arr_x][arr_y];
            //分配
            for (int item : unsorted) {
                int temp = (item / (int) Math.pow(10, i)) % 10;
                for (int j = 0; j < arr_y; j++) {
                    if (bucket[temp][j] == 0) {
                        bucket[temp][j] = item;
                        break;
                    }
                }
            }
            //收集
            for (int o = 0, x = 0; x < arr_x; x++) {
                for (int y = 0; y < arr_y; y++) {
                    if (bucket[x][y] == 0) {
                        continue;
                    }
                    unsorted[o++] = bucket[x][y];
                }
            }
        }
    }

    public static void main(String[] args) {
        //定义待排整型数组
        int[] arr = {21, 56, 88, 195, 354, 1, 35, 12, 6, 7};
        System.out.println("**************基数排序******************");
        System.out.println("排序前：");
        CommonUtils.display(arr);
        //调用基数排序函数
        radixSort(arr, 3);
        System.out.println("排序后：");
        //输出排序后的数组
        CommonUtils.display(arr);
        System.out.println("   ");
        int[] unsorted = {999999999, 65, 24, 47, 13, 50, 92, 88, 66, 33, 22445, 10001, 624159, 624158, 624155501};
        System.out.println("**************二维数组方式实现的基数排序******************");
        System.out.println("排序前：");
        CommonUtils.display(unsorted);
        radix_sort(unsorted, 10, 100);
        System.out.println("排序后：");
        for (int tmp : unsorted) {
            if (tmp > 0) {
                System.out.print(tmp + "  ");
            }
        }
    }
}

测试结果