棋牌游戏常用排序算法

一、介绍

棋牌游戏常用排序算法包括：链式基数排序、插入排序、希尔排序。

二、链式基数排序

1、基本思想

基数排序（Radix sort）属于“分配式排序”（distribution sort），它根据数据元素的某一特征将这些元素分成m组，然后再根据另一特征对组中的元素进行排序，即将一组数据变成m组排好序的数据。基数排序法是属于稳定性的排序。

链式基数排序是按数据元素特征的优先级排序的基数排序，先按低优先级的特征，将这些元素分成m组，然后按照一定的顺序将它们串联成一组数据；然后再按高优先级的特征进行分组和串联。这样排好序后，就变成按多特征排序的一组数据。

链式基数排序用于棋牌游戏洗牌。

2、代码实现

/**
 * 这里以麻将的排序来说明
 * @param list 麻将集合
 */
public static void linkedRadixSort(LinkedList<MaJiang> list) {
    if (Tool.isEmpty(list)) {
        return;
    }

    //先按点数分组
    LinkedList<MaJiang>[] rankList = new LinkedList[9];
    for (int i = 0; i < rankList.length; i++) {
        rankList[i] = new LinkedList<MaJiang>();
    }
    //按点数添加数据
    while (list.size() > 0) {
        MaJiang mj = list.remove();
        rankList[mj.rank - 1].add(mj);
    }
    //合并分组
    for (int i = 0; i < rankList.length; i++) {
        list.addAll(rankList[i]);
    }

    // 再按花色分组
    rankList = new LinkedList[3];
    for (int i = 0; i < rankList.length; i++) {
        rankList[i] = new LinkedList<MaJiang>();
    }
    //按花色添加数据
    while (list.size() > 0) {
        MaJiang mj = list.remove();
        rankList[mj.suit - 1].add(mj);
    }
    //合并分组
    for (int i = 0; i < rankList.length; i++) {
        list.addAll(rankList[i]);
    }
}

三、插入排序

1、基本思想

插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

插入排序适用于几乎已经排好序的数据，比如：棋牌游戏的插牌。

2、代码实现

/**
 * @param arr 要排序的数组
 */
public static <E extends Comparable<E>> void insertSort(E[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }
    //从前往后排序，先把前面所有的元素排好序，然后把后面的元素插到前面拍好的队列中
    for (int i = 1; i < arr.length; i++) {
        E temp = arr[i];
        int j = i;
        //找到需要插入的位置
        while (j > 0 && temp.compareTo(arr[j - 1]) < 0) {
            //后移一位
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = temp;
    }
}

四、希尔排序

1、基本思想

希尔排序(Shell's Sort)是将整个有序序列分割成若干小的子序列分别进行插入排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

排序过程：先取一个小于n的整数d1作为第一个增量(也叫步长)，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

希尔排序适合数组大部分有序的情况。希尔排序的效率还跟它的增量有关，适合的增量为：1,4,10,100..

2、代码实现

/**
 * @param arr 要排序的数组
 */
public static <E extends Comparable<E>> void shellSort(E[] arr) {
    if (Tool.isEmpty(arr)) {
        return;
    }
    shellSort(arr, 4);
    shellSort(arr, 1);
}

/**
 * 按步长进行希尔排序
 * @param arr  要排序的数组
 * @param step 步长
 */
public static <E extends Comparable<E>> void shellSort(E[] arr, int step) {
    if (Tool.isEmpty(arr)) {
        return;
    }
    for (int m = 0; m < step; m++) {
        for (int i = m + step; i < arr.length; i += step) {
            E temp = arr[i];
            int j = i;
            //与上一个步长的数据比较
            while (j - step >= 0 && temp.compareTo(arr[j - step]) < 0) {
                //后移一个步长位
                arr[j] = arr[j - step];
                j -= step;
            }
            arr[j] = temp;
        }
    }

}