基数排序（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]);
}
}
链式基数排序的应用场景：斗地主纸牌游戏，麻将初始化的排序，不适用于在打麻将过程中摸一张打一张的排序。
小白总结，往大神指点。
网友评论