快速排序：高性能排序算法的核心，吃透 “分治 + 分区” 逻辑

快速排序是工业界应用最广的排序算法之一，凭借 O (n log n) 的平均时间复杂度、原地排序的特性，成为实际开发中排序的首选方案。它以 “分治” 为核心思想，通过 “分区” 操作将数组拆分为子区间递归排序，是理解高级排序算法的关键。这篇文章带你掌握快速排序的原理、核心实现，以及优化要点。

一、快速排序是什么？

快速排序，核心是 “快”—— 通过分治思想 + 分区操作，将大问题拆解为小问题：选择一个 “基准值”，把数组分为 “小于基准值”“等于基准值”“大于基准值” 三个部分，再递归处理左右子区间，直到整个数组有序。

核心思想：
1、选基准：从数组中选一个元素作为「基准值（pivot）」；
2、分区：遍历数组，将小于基准的放左边，大于基准的放右边，基准归位；
3、递归：对左右两个子区间重复上述步骤，直到子区间长度为 1（天然有序）。

效率与特性：

• 时间复杂度：O(n log n)（平均 / 最优），最坏 O (n²)（已排序数组，需优化基准选择）
• 空间复杂度：O(log n)（递归栈空间，原地排序）
• 排序特性：不稳定排序（相等元素相对位置可能改变）、原地排序

适用场景：
适合大规模数据排序（百万级以上），是 JDK Arrays.sort() 底层排序的核心实现（基本类型）。

二、核心实现方式（经典单边分区）

快速排序的核心是 “分区函数”，以下是最易理解的经典单边分区实现，适配新手入门：

public class QuickSort {
    // 对外暴露的排序方法
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 递归入口：处理整个数组（左边界0，右边界arr.length-1）
        quickSortRecursive(arr, 0, arr.length - 1);
    }

    // 递归核心方法：处理 [left, right] 区间的元素
    private static void quickSortRecursive(int[] arr, int left, int right) {
        // 终止条件：区间只有1个元素或无元素
        if (left >= right) {
            return;
        }
        // 1. 分区：返回基准值的最终位置
        int pivotIndex = partition(arr, left, right);
        // 2. 递归处理左半区（小于基准）
        quickSortRecursive(arr, left, pivotIndex - 1);
        // 3. 递归处理右半区（大于基准）
        quickSortRecursive(arr, pivotIndex + 1, right);
    }

    // 分区核心：把[left, right]按基准值分成两部分，返回基准的最终位置
    private static int partition(int[] arr, int left, int right) {
        // 三数取中选基准值索引
        int pivotPos = getPivotIndex(nums, left, right);
        // 基准值交换到右边界
        swap(nums, pivotPos, right);

        // 选最右侧元素作为基准值
        int pivot = arr[right];
        // 「小于基准区」的右边界（初始为left-1，代表暂无元素）
        int i = left - 1;

        // 遍历[left, right-1]的所有元素
        for (int j = left; j < right; j++) {
            // 如果当前元素≤基准，放入「小于基准区」
            if (arr[j] <= pivot) {
                i++; // 扩大「小于基准区」
                swap(arr, i, j); // 把当前元素换到「小于基准区」的末尾
            }
        }
        // 把基准值放到「小于基准区」的下一个位置（基准的最终正确位置）
        swap(arr, i + 1, right);
        // 返回基准的位置
        return i + 1;
    }

    // 选择left、mid、right中大小居中的元素索引
    private int getPivotIndex(int[] nums, int left, int right) {
        int mid = left + (right - left) / 2;
       
        if ((nums[left] < nums[mid] && nums[mid] < nums[right]) || 
            (nums[left] > nums[mid] && nums[mid] > nums[right])) {
            return mid;
        } else if ((nums[mid] < nums[left] && nums[left] < nums[right]) || 
                   (nums[mid] > nums[left] && nums[left] > nums[right])) {
            return left;
        } else {
            return right;
        }
    }

    // 辅助交换方法
    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    // 测试
    public static void main(String[] args) {
        int[] arr = {9,8,7,6,5,4,3,2,1};
        System.out.println("排序前：" + java.util.Arrays.toString(arr));
        quickSort(arr);
        System.out.println("排序后：" + java.util.Arrays.toString(arr));
    }
}

三、必避的三个核心坑

快速排序代码看似简洁，但新手易踩这些关键坑，记住这 3 点：
1、基准选择问题： 若选固定边界（如右边界），对已排序数组会导致最坏时间复杂度 O (n²)，建议用「三数取中法」（选左、中、右中间值）或随机选基准；
2、递归栈溢出： 极端场景下递归深度可达 n，可限制递归深度（如子区间长度 < 10 时改用插入排序），或手动实现非递归版；
3、分区边界： 遍历区间必须是 [left, right-1]，而非 [left, right]，否则会重复处理基准值导致死循环。

四、关键优化（工程级实现要点）

经典版快速排序可通过以下优化适配工业场景：
重复元素优化：三路快排

两者比较：

• 普通快排：跳过 1 个基准值
• 三路快排：跳过 一整块基准区

将数组分为 “小于、等于、大于” 基准三部分，避免重复元素导致的分区失衡。

import java.util.Random;

class Solution {
    private Random random = new Random();

    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        // 1. 随机选取基准值，并把它交换到最右侧 (避免有序数组退化)
        int pivotIndex = left + random.nextInt(right - left + 1);
        swap(nums, pivotIndex, right);

        // 2. 三路划分 (处理重复元素)
        int pivotValue = nums[right];
        int less = left;      // 小于区域的右边界
        int greater = right;   // 大于区域的左边界
        int i = left;         // 当前遍历的指针

        while (i <= greater) {
            if (nums[i] < pivotValue) {
                // 当前数小于基准，把它扔到小于区域，i 和 less 都前进
                swap(nums, i++, less++);
            } else if (nums[i] > pivotValue) {
                // 当前数大于基准，把它扔到大于区域
                // 注意：交换过来一个新的数，i 暂时不能前进，下一轮要继续判断它
                swap(nums, i, greater--);
            } else {
                // 等于基准，仅 i 前进
                i++;
            }
        }

        // 经过三路划分后，数组变成了：
        // [l, less-1] 是 < pivot 的
        // [less, greater] 是 == pivot 的  <-- 这部分已经排好了，不需要再管！
        // [greater+1, r] 是 > pivot 的

        // 3. 递归左右两侧
        quickSort(nums, left, less - 1);
        quickSort(nums, greater + 1, right);
    }

    private void swap(int[] nums, int i, int j) {
        if (i == j) {
            return;
        }

        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

五、总结

1、快速排序核心逻辑是 “分治 + 分区”，通过基准值将数组拆分为子区间递归排序，平均时间复杂度 O (n log n)；
2、经典版快速排序易因基准选择不当触发最坏情况，工程中需做三数取中、小区间优化；
3、核心避坑点是基准选择、递归终止条件、分区边界，避免栈溢出和死循环。