知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 08 - 手撕快速排序 ## 题目(补充题4) 实现快速排序算法。 ## 解法 ```java class Solution { public int[] sortArray(int[] nums) { quickSort(nums, 0, nums.length - 1); return nums; } private void quickSort(int[] nums, int lo, int hi) { if (lo >= hi) return; int pivot = partition(nums, lo, hi); quickSort(nums, lo, pivot - 1); quickSort(nums, pivot + 1, hi); } private int partition(int[] nums, int lo, int hi) { int rand = lo + new Random().nextInt(hi - lo + 1); swap(nums, rand, hi); int pivot = nums[hi], i = lo; for (int j = lo; j < hi; j++) { if (nums[j] <= pivot) swap(nums, i++, j); } swap(nums, i, hi); return i; } private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } } ``` > 💬 **Q:解释这段快排代码,partition 不好理解** > > 整体流程:选一个基准值 pivot → 把数组分成 "≤pivot" 和 ">pivot" 两部分 → 递归排序两部分。 > > partition 的核心是用 `i` 指针维护一个边界:**`[lo, i)` 区间内的元素都 ≤ pivot**。 > > 用 `[3, 6, 2, 7, 1]` 模拟(假设随机选中 3,swap 到末尾后 `[1, 6, 2, 7, 3]`,pivot=3): > > ``` > 初始: i=0, pivot=3 > 数组: [1, 6, 2, 7, 3] > j > > j=0: nums[0]=1 ≤ 3 → swap(0,0), i→1 > [1, 6, 2, 7, 3] i指向6 > > j=1: nums[1]=6 > 3 → 跳过 > > j=2: nums[2]=2 ≤ 3 → swap(1,2), i→2 > [1, 2, 6, 7, 3] 把2换到前面,i指向6 > > j=3: nums[3]=7 > 3 → 跳过 > > 循环结束,swap(i=2, hi=4):pivot归位 > [1, 2, 3, 7, 6] > ↑ > 返回 i=2 > ``` > > 结果:i 左边 `[1,2]` 都 ≤ 3,右边 `[7,6]` 都 > 3。 > > 关键理解: > - `i` = "下一个该放小元素的位置" > - `j` 扫到一个 ≤ pivot 的元素 → 换到 `i` 位置 → `i` 前推一格 > - 最后把 pivot(在末尾)换到 `i` 位置 → pivot 归位 > - 随机选 pivot 再 swap 到末尾,是为了避免有序数组导致 O(n²) 最坏情况 ## 复杂度 - 平均 O(n log n),最坏 O(n²),空间 O(log n) ## 一句话总结 选 pivot 分区,小的放左边大的放右边,递归处理两半。随机化 pivot 避免最坏情况。 ## 解法二:归并排序 稳定排序,最坏情况也是 O(n log n),但需要额外空间。 ```java class Solution { public int[] sortArray(int[] nums) { mergeSort(nums, 0, nums.length - 1); return nums; } private void mergeSort(int[] nums, int lo, int hi) { if (lo >= hi) return; int mid = lo + (hi - lo) / 2; mergeSort(nums, lo, mid); mergeSort(nums, mid + 1, hi); merge(nums, lo, mid, hi); } private void merge(int[] nums, int lo, int mid, int hi) { int[] tmp = Arrays.copyOfRange(nums, lo, hi + 1); int i = 0, j = mid - lo + 1, k = lo; while (i <= mid - lo && j <= hi - lo) { if (tmp[i] <= tmp[j]) nums[k++] = tmp[i++]; else nums[k++] = tmp[j++]; } while (i <= mid - lo) nums[k++] = tmp[i++]; while (j <= hi - lo) nums[k++] = tmp[j++]; } } ``` ## 解法对比 | | 解法一(快速排序) | 解法二(归并排序) | |--|--------|--------| | 时间复杂度 | 平均 O(n log n),最坏 O(n²) | O(n log n) | | 空间复杂度 | O(log n) | O(n) | | 特点 | 原地,缓存友好,不稳定 | 稳定,最坏有保证,需额外空间 |
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入