算法04-棋牌游戏常用排序算法

一、介绍

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

二、链式基数排序

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
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

三、插入排序

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
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

四、希尔排序

1、基本思想

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

排序过程:先取一个小于n的整数d1作为第一个增量(也叫步长),把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2

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;
        }
    }

}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

demo已上传gitee,需要的同学可以下载!