算法（一）之排序算法（五）——链式基数排序（LinkedRadi

基数排序（RadixSort）也是八大排序算法之一，它在棋牌游戏中的应用非常常见。基数排序是采用“分配”与“收集”的办法，用对多关键码进行排序的思想实现对单关键码进行排序的方法。我们这里只分析在平常开发生活中会用到的场景，而不具体去研究。

思路：使用链表存储数据，通过调整指针实现LSD（低关键字优先）算法进行排序。

举个例子就是我们在qq游戏上的纸牌或麻将，从服务器端返回来一组数据，纸牌和麻将都是多关键字的对象，纸牌和麻将都是有点数和花色划分的，我们要对这组数据进行排序，那使用链式基数排序效率是最快的。
而且这种排序是使用在对原始数据的排序，如果有新数据添加进来的话，那就使用希尔排序。

以麻将为例，请看图：

（1）先初始化一个要存放的点数的集合数组，根据点数把数据放入对应的数组中，把点数为1的数放入数组为0的下标中, 点数为2的数据放入1的下标中，数组中每个下标存放数据的都是一个集合，这样就可以把数值为1~9的麻将分别存入对应的数组中。然后再把数组中的集合按顺序依次添加到一个新的集合中。

（2）初始化一个存放花色的集合数组，根据花色把数据放入对应的组中，把花色为万字的数据放入数组为0的下标中，花色为条字的数据放入数组为1的下标中，花色为筒字的数据放入数组为2的下标中，这样就可以把花色为万筒条的数据都存入对应的数组中。最后再把数组中的集合桉树按顺序依次添加到一个新的集合当中。

这样就完成了麻将的排序。光说也是说不清楚的，我们来看代码就知道是怎么回事了。

1.先定义一个麻将的实体类：

static class Mahjong{
    int suit;   //花色 万 筒 条
    int rank;   //点数大小

    public Mahjong(int suit,int rank){
        this.suit = suit;
        this.rank = rank;
    }
}

2.然后模拟一组麻将数据：

  SinglyLinkedList<Mahjong> list = new SinglyLinkedList<>();  //使用单链表，因为效率最高
    list.add(new Mahjong(3,1));
    list.add(new Mahjong(2,3));
    list.add(new Mahjong(3,7));
    list.add(new Mahjong(1,1));
    list.add(new Mahjong(3,8));
    list.add(new Mahjong(2,2));
    list.add(new Mahjong(3,2));
    list.add(new Mahjong(1,3));
    list.add(new Mahjong(3,9));

    radixSort(list);

这里就不打印了，有兴趣的同志可以自己参照思路进行实现。

3.然后对麻将集合进行链式基数排序

  public static void radixSort(SinglyLinkedList<Mahjong> list){
    //step1:先初始化要存放点数的集合数组
    SinglyLinkedList[] rankList = new SinglyLinkedList[9];

    for(int i=0;i<rankList.length;i++){
        rankList[i] = new SinglyLinkedList();  //让每个数组都放置单链表集合
    }

    //step2: 根据点数把数据放入对应的组中 把点数为1放入数组0, 2的放入1......
    while (list.size() > 0){
        Mahjong mahjong = list.remove();    //注意这里是把数据进行删除，也可以用get方法，为了方便下面我直接用的删除
        rankList[mahjong.rank - 1].add(mahjong);    //麻将的点数-1就是放入对应的数组下标，因为麻将是从1开始的
    }

    //step3:把9个组的数据连接起来形成一个单链表，这里就用原来的list进行存储，因为上面已经取空了
    for(int i=0;i<rankList.length;i++){
        list.addAll(rankList[i]);
    }

    //step4:初始化要存放花色的集合数组，这个逻辑和上面存放点数的是一样的
    SinglyLinkedList[] suitList = new SinglyLinkedList[3];
    for (int i=0;i<suitList.length;i++){
        suitList[i] = new SinglyLinkedList();
    }

    //step5:根据花色把数据放入对应的组中，花色为1放入0.。。。。。
    while (list.size() > 0){
        Mahjong mahjong = list.remove();
        suitList[mahjong.suit - 1].add(mahjong);
    }

    //step6:把3个组的数据连接起来形成一个单链表，最后list存放的就是我们排好点数和花色的数据
    for(int i=0;i<suitList.length;i++){
        list.addAll(suitList[i]);
    }
}

链式基数排序的应用场景：斗地主纸牌游戏，麻将初始化的排序，不适用于在打麻将过程中摸一张打一张的排序。

小白总结，往大神指点。