如何通俗易懂理解快速排序(快排)？

### **通俗易懂理解快速排序（QuickSort）** 快速排序（QuickSort）可以理解为“**分堆排队**”的过程： 1. **选一个基准值（pivot）**：比如随便选一个数。 2. **分区（Partition）**： - **比 pivot 小的放左边**，**比 pivot 大的放右边**。 3. **递归处理左右两部分**，直到整个数组有序。  ### **快速排序 Java 实现** ```java public class QuickSort { public static void quickSort(int[] arr, int left, int right) { if (left >= right) return; // 递归终止条件 int pivotIndex = partition(arr, left, right); // 分区 quickSort(arr, left, pivotIndex - 1); // 递归排序左半部分 quickSort(arr, pivotIndex + 1, right); // 递归排序右半部分 } private static int partition(int[] arr, int left, int right) { int pivot = arr[right]; // 选择最后一个元素作为基准 int i = left - 1; // i 指向小于 pivot 的区间 for (int j = left; j < right; j++) { if (arr[j] < pivot) { // 当前元素小于 pivot i++; swap(arr, i, j); } } swap(arr, i + 1, right); // 把 pivot 放到正确位置 return i + 1; // 返回 pivot 的最终位置 } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args) { int[] arr = {6, 1, 7, 9, 3, 8, 2, 5}; quickSort(arr, 0, arr.length - 1); for (int num : arr) { System.out.print(num + " "); } } } ``` ### **代码讲解** 1. **递归方法 `quickSort`**： - 先**分区**，找到 `pivot` 的最终位置。 - 递归对 `pivot` 左右的部分分别排序。 2. **`partition` 方法（分区）**： - 选择 `pivot`（这里选最后一个元素）。 - 遍历数组，把比 `pivot` 小的放左边，比 `pivot` 大的放右边。 - 交换 `pivot` 让它回到正确位置，并返回索引。 3. **交换方法 `swap`**： - 交换 `i` 和 `j` 位置的值，辅助 `partition` 操作。 ### **时间复杂度分析** - **平均情况**：`O(n log n)`（每次分区 `O(n)`，递归 `log n` 层） - **最坏情况**：`O(n²)`（数组已排序，每次选最小/最大值） ### **优化方案** - **随机选择 pivot**（避免最坏情况）。 - **三数取中法**（选择 `left`、`mid`、`right` 中间值）。 ### **总结** - **找一个基准值**，让**小的放左边，大的放右边**。 - **递归处理左右两部分**，最终数组有序。 - **时间复杂度 `O(n log n)`，最坏 `O(n²)`**。