【排序】快速排序

思想

快速排序是一种基于分治策略的排序算法，其核心思想通过选取一个基准元素，将数组分成两个子数组：一个包含小于基准元素的值，另一个包含大于基准元素的值。然后递归地对这两个子数组进行排序，最终将它们合并起来，得到有序的数组。

图解实现

在这里插入图片描述

具体代码实现

public static int[] quickSort(int[] arr, int leftIndex, int rightIndex) {
    // 递归结束条件 左边索引小于右边索引
    if (leftIndex < rightIndex) {
        // 通过分区函数得到基准元素的索引
        int pivotIndex = partition(arr, leftIndex, rightIndex);
        //递归对基准元素左边的子数组进行快速排序
        quickSort(arr, leftIndex, pivotIndex - 1);
        //递归对基准元素右边的子数组进行快速排序
        quickSort(arr, pivotIndex + 1, rightIndex);
    }
    return arr;
}

/**
 * 分区函数
 *
 * @param arr        数组
 * @param leftIndex  左索引
 * @param rightIndex 右索引
 * @return 返回基准元素的索引
 */
private static int partition(int[] arr, int leftIndex, int rightIndex) {
    // 基准元素是最后一个元素
    int baseNum = arr[rightIndex];
    // 左边索引小于右边索引就一直循环
    while (leftIndex < rightIndex) {
        // l < r 且 左边的元素一直小于基准元素，左边索引做加1操作（因为要放在基准元素左边）
        while (leftIndex < rightIndex && arr[leftIndex] <= baseNum) {
            leftIndex++;
        }
        // 如果不满足上边条件，说明此时这个值要比基准元素大，就放在基准元素右边。把左边元素值直接赋给右边即可（注意基准元素全局不参与运算，存在的意义只是比较而已）
        arr[rightIndex] = arr[leftIndex];
        // l < r 且 右边的元素一直大于基准元素，右边索引做减1操作（因为要放在基准元素右边）
        while (leftIndex < rightIndex && arr[rightIndex] >= baseNum) {
            rightIndex--;
        }
        // 如果不满足上边条件，说明此时这个值要比基准元素小，就放在基准元素左边。把右边元素值直接赋给左边即可
        arr[leftIndex] = arr[rightIndex];
    }
    // 走到这里说明 leftIndex < rightIndex 这个条件就不满足了，也就是说 leftIndex = rightIndex，这个时候把基准元素的值复制在这个位置即可，
    // 并返回此时这个位置的索引即可。
    arr[leftIndex] = baseNum;
    return leftIndex;
}