Java深入浅出理解快速排序以及优化方式

快速排序简介

快速排序是一种常用的排序算法，它的基本思想是选定一个基准数，通过递归的方式将比基准数小的值放在其左侧，比基准数大的值放在其右侧，最终达到排序的效果。快速排序的时间复杂度为O(nlogn)，是一种比较快速有效的排序算法。

快速排序基本流程

1. 选择一个基准数，例如选定数组的最后一个元素作为基准数；
2. 遍历数组，将比基准数小的元素移到基准数的左侧，大于或等于基准数的元素移到右侧，可以使用两个指针 low 和 high 分别指向数组的两端，通过交换元素位置实现；
3. 分别对基准数左侧和右侧的子数组递归执行上述操作，直到完成整个数组排序。

快速排序优化

虽然快速排序是一种高效的算法，但是在实际应用中，还需要进一步优化以提高排序效率和稳定性。

1. 随机化

快速排序的时间复杂度和初始序列的顺序有关，如果序列本身就是有序的或者基本有序的，那么快速排序的效率会大打折扣，甚至会退化到O(n^2)的时间复杂度。为了避免这种情况，可以引入随机化的思想，在排序之前随机选择一个元素作为基准数，降低排序的时间复杂度和随机性。

2. 三点取中法

在选择基准数的时候，如果选择的数刚好是序列的最大值或最小值，则快速排序的效率也会受到影响。在这种情况下，可以采用“三点取中法”，即选择序列的左端、右端和中间元素的中位数作为基准数。

示例说明

示例1：快速排序基本流程

/**
 * 快速排序基本流程
 * 
 * @param arr 待排序的数组
 * @param low 排序起始位置
 * @param high 排序终止位置
 */
public static void quickSort(int[] arr, int low, int high) {
    if (low >= high) { // 当数组长度为1或0时，已经排序完成
        return;
    }
    int i = low;
    int j = high;
    int pivot = arr[high]; // 选择最后一个元素作为基准数
    while (i < j) {
        while (i < j && arr[i] < pivot) { // 从左往右找第一个大于等于pivot的位置
            i++;
        }
        while (i < j && arr[j] >= pivot) { // 从右往左找第一个小于pivot的位置
            j--;
        }
        if (i < j) { // 交换i和j位置的元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    arr[high] = arr[i]; // 将基准数放到正确的位置上
    arr[i] = pivot;
    quickSort(arr, low, i - 1); // 对基准数左侧的数组递归执行快速排序
    quickSort(arr, i + 1, high); // 对基准数右侧的数组递归执行快速排序
}

示例2：快速排序优化

/**
 * 快速排序优化
 * 
 * @param arr 待排序的数组
 * @param low 排序起始位置
 * @param high 排序终止位置
 */
public static void quickSort(int[] arr, int low, int high) {
    if (low >= high) {
        return;
    }
    int i = low;
    int j = high;
    int pivot = medianOfThree(arr, low, high); // 选择中位数作为基准数
    while (i < j) {
        while (i < j && arr[i] < pivot) {
            i++;
        }
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        if (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    arr[high] = arr[i];
    arr[i] = pivot;
    quickSort(arr, low, i - 1);
    quickSort(arr, i + 1, high);
}

/**
 * 三点取中法
 * 
 * @param arr 待排序的数组
 * @param low 排序起始位置
 * @param high 排序终止位置
 * @return 中位数
 */
private static int medianOfThree(int[] arr, int low, int high) {
    int mid = low + (high - low) / 2;
    if (arr[low] > arr[high]) {
        swap(arr, low, high);
    }
    if (arr[mid] > arr[high]) {
        swap(arr, mid, high);
    }
    if (arr[low] > arr[mid]) {
        swap(arr, low, mid);
    }
    return arr[mid];
}

/**
 * 交换数组中两个元素的位置
 * 
 * @param arr 待交换的数组
 * @param i 第一个元素的位置
 * @param j 第二个元素的位置
 */
private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}