一、核心思想分治思想选基准 (pivot)从数组中挑选一个元素作为基准值分区 (partition)把小于基准的元素放左边大于基准的放右边一轮结束后基准元素落在它最终正确位置递归基准左侧子数组、右侧子数组重复上面两步直到子数组长度 ≤ 1天然有序。算法特性平均时间复杂度\(O(nlogn)\)最坏时间复杂度\(O(n^2)\)如已有序数组选最左当基准空间复杂度\(O(logn)\) 递归栈不稳定排序二、实现方式左右指针法最常考java运行public class QuickSort { public static void main(String[] args) { int[] arr {4, 7, 2, 9, 1, 5, 8, 3, 6}; System.out.println(排序前); printArr(arr); quickSort(arr, 0, arr.length - 1); System.out.println(排序后); printArr(arr); } /** * 快速排序递归入口 * param arr 数组 * param left 左边界下标 * param right 右边界下标 */ public static void quickSort(int[] arr, int left, int right) { // 递归终止条件区间只有一个元素或不存在元素 if (left right) { return; } // 分区返回基准元素最终位置 int pivotIndex partition(arr, left, right); // 递归处理左区间 [left, pivotIndex-1] quickSort(arr, left, pivotIndex - 1); // 递归处理右区间 [pivotIndex1, right] quickSort(arr, pivotIndex 1, right); } /** * 分区函数左右指针法以最左侧元素为基准 */ public static int partition(int[] arr, int left, int right) { // 选取最左边元素作为基准 int pivot arr[left]; int i left; int j right; while (i j) { // 右指针往左找找到 小于pivot 的元素 while (i j arr[j] pivot) { j--; } // 将找到的小数放到i位置 arr[i] arr[j]; // 左指针往右找找到 大于pivot 的元素 while (i j arr[i] pivot) { i; } // 将找到的大数放到j位置 arr[j] arr[i]; } // i j基准放入最终位置 arr[i] pivot; return i; } // 打印数组 public static void printArr(int[] arr) { for (int num : arr) { System.out.print(num ); } System.out.println(); } }三、分区流程简单演示数组[4,7,2,9,1]pivot 4j 向左找到 1放到 i 位置 →[1,7,2,9,1]i 向右找到 7放到 j 位置 →[1,7,2,9,7]j 向左找到 2放到 i 位置 →[1,2,2,9,7]i 继续右移ij填入基准 4 →[1,2,4,9,7]基准 4 就位再递归排序[1,2]和[9,7]四、常见优化点面试加分基准优化不要固定选最左采用「三数取中法」(左端、右端、中间选中位数当 pivot)避免有序数组触发最坏情况小区间优化当子数组长度很小如长度 10改用插入排序减少递归开销处理重复元素三路快排小于、等于、大于基准三段大量重复数据时效率大幅提升。
