排序算法系列二：归并排序、快速排序

零、说在前面

        本文是一个系列， 入口请移步这里

一、理论部分

1.4：归并排序

1.4.1：算法解读：

        使用二分法和插入排序两种算法的思想来实现。流程分为“拆分”、“合并”两大部分，前者就是普通的二分思想，将一个数组拆成n个子组；后者是在每个子组内部用插入法排序，在子组间定义一个辅助数组和三个指针，用辅助数组搭配指针选数进行排序，再将两个子组合并；最终将所有子组合并成一个有序的数组。

1.4.2：时间复杂度

        因为用到了分治思想，因此时间复杂度除了与数据量有关，还与遍历次数（即对数据量二分次数 logN ）有关，因此时间复杂度为 O(N logN)

        在最优与最坏情况，二分操作耗时不会节约、归并比较阶段操作耗时不会节约，因此在遍历的数据量不变，遍历的轮次不变的情况下，时间复杂度固定为O(N logN)

1.4.3：优缺点：

        算法耗时稳定，但需要额外的辅助空间，需付出空间复杂度的代价。适用于大数据量的排序

1.4.4：代码：

/**
 * date:    2024-06-23
 * author:  dark
 * description: 归并排序算法（由小到大）
 */
public class Merge {
 
    /**
     * 定义原始数组长度
     */
    public static int arrayLength;
 
    /**
     * 定义临时数组
     */
    public static Integer[] tempArrays;
 
    /**
     * 定义临时变量
     */
    public static int tempArrayPointer = 0;
 
    /**
     * 逻辑步骤：1：接受一个数组，对它进行两步操作，即 先拆分后归并。并开辟一个与原数组等长的临时数组和四个指针
     *         2：拆分：用数组的中间坐标作为拆分的边界，并将得到的两个子数组递归拆分，直至每个子组元素小于等于2为止，并保证组内元素有序。
     *         3：归并：从左向右，选择相邻的两个子组，令三个指针分别指向这两个子组的首元素坐标位置、以及左子组坐标对应临时坐标中的位置。
     *                对两个子组的元素两两比较，将其中较小的元素拷贝到临时数组中，并控制较小元素所在子组的指针和临时数组的指针右移一位。
     *                直至这两个子组的元素比对完毕，然后将这对子组进行拼接并将临时数组中的元素对位拷贝到新子组中。
     *                以此类推处理同级别的所有子组，并递归处理合并后的子组，直至将所有子组合并成一个有序数组。
     *          4：注意：为逻辑方便，整个流程的右子数组的终止位置设置在数组越界1位的位置 使用时需谨慎
     * @param arrays
     */
    public void mergeSort(Integer[] arrays){
        arrayLength = arrays.length;
        /**
         * 定义左、右子组的首元素指针、右子组的尾部指针，并为临时数组指针赋初值。
         * 右指针的起始位置根据数组长度加1除2后确定，这样得到的右子组位置略偏右
         * 为了后续逻辑方便，特将 数组终止位置坐标 设置为 数组实际长度
         */
        int startPointer = 0,  endPointer = arrayLength;
        tempArrays = new Integer[arrayLength];
 
        split(arrays, startPointer, endPointer);
    }
 
    /**
     * 拆分。当传入的子组元素数量小于等于2时，进行合并（原因是避免 当待拆分元素是3个时，给后续操作带来困难）
     *      否则递归调用本方法继续拆分。注意：应通过准确计算左右索引的位置控制拆分的准确
     * @param arrays
     * @param startPointer
     * @param endPointer
     */
    public void split(Integer[] arrays, int startPointer, int endPointer){
 
        /**
         * 因为传入的 endPointer 的坐标处于数组越界1位的位置，
         * 因此作为右子数组的起始位置的  middlePointer 等于 起点与终点坐标之和的 二分之一
         */
        int middlePointer = (startPointer + endPointer)/2 ;
        /**
         *
         * 因此下面的逻辑判断我交给 if 判断来使用， 而非交给 while 来使用
         * 又因为startPointer 是从0开始计数，因此下面的逻辑判断的实际意义是：
         * 当数组中大于3个元素需要继续拆分，否则就可以归并了
         */
        if(endPointer-startPointer > 2) {
            /**
             * 二分拆解原数组，通过计算得到两个子组各自的左右指针坐标
             */
            split(arrays, startPointer, middlePointer);
            split(arrays, middlePointer, endPointer);
        }
        merge(arrays, startPointer, middlePointer, endPointer);
    }
 
    /**
     * 归并：    从左向右，选择相邻的两个子组，令三个指针分别指向这两个子组的首元素坐标位置、以及左子组坐标对应临时坐标中的位置。
     *          对两个子组的元素两两比较，将其中较小的元素拷贝到临时数组中，并控制较小元素所在子组的指针和临时数组的指针右移一位。
     *          直至这两个子组的元素比对完毕，然后将这对子组进行拼接并将临时数组中的元素对位拷贝到原数组中。
     *          以此类推处理同级别的所有子组，并递归处理合并后的子组，直至将所有子组合并成一个有序数组。
     * @param arrays
     * @param startPointer      左子数组起始位指针
     * @param middlePointer     右子数组起始位指针
     * @param endPointer        右子数组终止位指针（这个参数应始终保持处于越界1位的位置，这样便于判断 middlePointer 是否越界）
     */
    public void merge(Integer[] arrays, int startPointer, int middlePointer, int endPointer){
        /**
         * 定义 右子数组的起始位副本，用来判断 startPointer 与 middlePointer 是否越界
         * 定义 左子数组的起始位副本，用来循环将副本数组的数据同步到原始数组中。
         * 临时数组指针，初始指向本次子数组首位
         */
        int startPointerTmp = startPointer, middlePointerTmp = middlePointer;
        tempArrayPointer = startPointer;
 
        /**
         * 当 两个指针都没越界，则执行下面逻辑，两个都临界/越界，则比对结束跳出循环
         */
        while(true){
            /**
             * 若左右指针都没越界，则通过比两个子数组元素的大小决定将谁放入临时数组
             * 若有一个指针临界或越界，则直接将另一个子数组的元素都放入临时数组即可
             */
            if(startPointer < middlePointerTmp && middlePointer < endPointer){
                if(arrays[startPointer] < arrays[middlePointer]){
                    tempArrays[tempArrayPointer++] = arrays[startPointer++];
                } else {
                    tempArrays[tempArrayPointer++] = arrays[middlePointer++];
                }
            } else if (startPointer == middlePointerTmp && middlePointer < endPointer) {
                while (middlePointer < endPointer){
                    tempArrays[tempArrayPointer++] = arrays[middlePointer++];
                }
            } else if (middlePointer == endPointer && startPointer < middlePointerTmp) {
                while (startPointer < middlePointerTmp){
                    tempArrays[tempArrayPointer++] = arrays[startPointer++];
                }
            } else {
                for (int i = startPointerTmp; i < endPointer; i++) {
                    arrays[i] = tempArrays[i];
                }
                break;
            }
        }
    }
}

1.5：快速排序

1.5.1：算法解读：

        在每轮循环中，以一个人为指定的元素作为数组的分界线，将当前数组中小于它的元素置于其左侧，大于的置于其右侧，形成两个子数组，再对两个子数组重复上述过程，直至无法细分为止，此时数组有序。

1.5.2：时间复杂度

        因为用到了分治思想，因此时间复杂度除了与数据量有关，还与遍历次数（即对数据量二分次数 logN ）有关，因此时间复杂度为 O(N logN)

        在最优情况下，左右指针应该在数组中间附近汇合，这样每次都能将数组二分，其时间复杂度为 O(N logN)，最坏情况下数据顺序倒排，每一轮的分界线都不能实现对数组的二分，算法会退化成类似选择排序的样子，时间复杂度为 O()

1.5.3：优缺点：

        在最优与最差情况下的表现差距较大，是一个不稳定的排序算法。适用于大数据量的排序。

1.5.4：代码：

/**
 * date:    2024-06-25
 * author:  dark
 * description: 快速排序算法（由小到大）
 */
public class Quick {
 
    /**
     * 初始数组长度
     */
    public Integer arrayLength = 0;
    /**
     * 定义向左（即找到比分界线更小元素）的指针 和 向右（更大元素）的指针
     */
    public Integer leftWardPointer, rightWardPointer;
    /**
     * 为便于后续数组内的数据交换，定义一个静态变量，作为接受外部数据的副本
     */
    private static Integer[] arrayLocal;
 
    /**
     * 逻辑步骤：1: 接受一个数组
     *         2: 从数组中选择一个随机数（比如首元素）作为分界线，目的是将数组中小于分界线的元素置于其左侧，大于的置于其右侧。
     *            定义两个临时指针分别指向数组的首尾（为方便后续逻辑，这里的尾指针指向的是尾元素的后一位）
     *            令左向和右向临时指针相向移动，理想状态下左向指针扫描过的都是大于分界线的数据，右向指针扫描的都是小于分界线数据
     *            因此当两个指针遇到非理想数据时停止扫描，交换两个临时指针对应的数据
     *               当左右指针相遇，说明二者扫过的都是符合理想状态的数据，且相遇点应该就是分界线指针所在位置。
     *            将分界线指针交换到二者相遇点即可。
     *            特殊情况一、左向指针移到头部也没遇到一个符合的数据，说明分界线就是当前数组最小的元素，毋需交换分界线位置
     *            特殊情况二、左向指针移动了一格，但右向指针与左向重合也没一个符合的数据，说明所有数据都小于分界线，
     *                      将分界线交换到数组尾部即可。
     *         3: 在左右子数组中递归重复步骤2的过程，直至子数组中仅剩一个元素，然后将左右子数组与各自的分界线进行归并。
     * @param arrays
     */
    public void quickSort(Integer[] arrays){
        arrayLength = arrays.length;
        arrayLocal = arrays;
        leftWardPointer = arrayLength;
        rightWardPointer = 0;
        exchangeLeftOrRight(arrayLocal, rightWardPointer, leftWardPointer);
    }
 
    /**
     * 以当前数组首元素为分界线，将以 leftWardPointer 为起点，以 rightWardPointer 为终点的数组拆分成左右两个子数组
     * @param arrays
     * @param leftWardPointer       位于数组尾部
     * @param rightWardPointer      位于数组首部
     */
    public void exchangeLeftOrRight(Integer[] arrays, Integer rightWardPointer, Integer leftWardPointer){
        /**
         * 分界线的初始位置 为右向指针的初始位置。
         */
        Integer boundaryPointer = rightWardPointer;
        Integer temp ;
        /**
         * 定义左右向指针的初始位置，以便递归使用
         */
        Integer leftWardPointerTmp = leftWardPointer, rightWardPointerTmp = rightWardPointer;
 
        /**
         * 每次遍历至少得有两个及以上元素才行
         */
        while(leftWardPointerTmp - rightWardPointerTmp >= 2){
            /**
             * 1：当左向指针 与 右向指针副本重合，说明到达了终点
             * 2：在左向指针移动中，若遇到小于分界线的元素，则记下当前指针位置并跳出循环，备用
             * 3：因为左向指针的初始值是 数组长度 ，因此可以先 ++ 再比对
             * 4：下面的 右向指针也是类似的逻辑
             */
            while(--leftWardPointer > rightWardPointer){
                if(arrayLocal[leftWardPointer] <= arrayLocal[boundaryPointer]) {
                    break;
                }
            }
            while(++rightWardPointer < leftWardPointer){
                if(arrayLocal[rightWardPointer] >= arrayLocal[boundaryPointer])
                break;
            }
            /**
             * 走到这里若左右指针尚未重合，说明可以交换二者指向的数据
             * 当左向指针位置小于等于右向指针，说明数组中数据分布符合分界线的要求
             * 此时将分界线交换到 左右向指针重合位置或左向指针(因此时右向跨越左向指针，说明右向指针走的有点儿多了，故而不选右指针的位置)的位置即可。
             * 即使左右向指针有一个没移动过也没关系，分析过程见“逻辑步骤”第二步的特殊情况分析
             */
            if(leftWardPointer > rightWardPointer ){
                temp = arrayLocal[leftWardPointer];
                arrayLocal[leftWardPointer] = arrayLocal[rightWardPointer];
                arrayLocal[rightWardPointer] = temp;
            } else if (leftWardPointer <= rightWardPointer) {
                temp = arrayLocal[boundaryPointer];
                arrayLocal[boundaryPointer] = arrayLocal[leftWardPointer];
                arrayLocal[leftWardPointer] = temp;
                boundaryPointer = leftWardPointer;
 
                /**
                 * 因为左向指针的特殊处理逻辑（从子数组长度+1开始算，因此下面第一行第三个参数不能传 boundaryPointer+1）
                 */
                exchangeLeftOrRight(arrayLocal, rightWardPointerTmp, boundaryPointer);
                exchangeLeftOrRight(arrayLocal, boundaryPointer+1, leftWardPointerTmp);
                break;
            }
        }
    }
}

二、对比

2.4：归并与快速

        二者都运用了分治思想，都适用于大量数据情况下的排序，前者在最优最差情况下表现稳定，后者表现不够稳定，在最差情况下会退化，使时间复杂度变为 O()

2.5：快速与希尔

        二者都运用了分治思想，都适用于大量数据情况下的排序，二者都是边比较边交换排序，后者在每轮循环中都会在小范围内使数据有序，因此在最差情况下的表现会优于快速排序。