排序数组
这是一道围绕数组、分治、桶排序展开的高频练习。建议先掌握「quick-sort」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
题目分析
这道题表面上是在处理「排序数组」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考 数组、分治 这些能力。排序在这里通常不是终点，而是把原本难处理的关系整理成更容易推进的顺序。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。
推荐代码
class Solution {
public int[] sortArray(int[] nums) {
randomizedQuicksort(nums, 0, nums.length - 1);
return nums;
}
public void randomizedQuicksort(int[] nums, int l, int r) {
if (l < r) {
int pos = randomizedPartition(nums, l, r);
randomizedQuicksort(nums, l, pos - 1);
randomizedQuicksort(nums, pos + 1, r);
}
}
public int randomizedPartition(int[] nums, int l, int r) {
int i = new Random().nextInt(r - l + 1) + l; // 随机选一个作为我们的主元
swap(nums, r, i);
return partition(nums, l, r);
}
public int partition(int[] nums, int l, int r) {
int pivot = nums[r];
int i = l - 1;
for (int j = l; j <= r - 1; ++j) {
if (nums[j] < pivot) {
i = i + 1;
swap(nums, i, j);
}
}
swap(nums, i + 1, r);
return i + 1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}结构化讲解
面试时怎么讲
开场思路
这题我会用快速排序，核心是 partition。
核心过程
- 先选一个基准值。
- 通过 partition 把小元素放左边、大元素放右边，并让基准值归位。
- 然后递归排序左右两个子区间。
- 区间长度缩到 1 时递归结束。
复杂度总结
平均时间复杂度 O(n log n)，空间复杂度 O(log n)。
核心思路
快速排序的核心不是“交换很多次”，而是用 partition 把一个基准值放到最终正确位置，并让左右两侧都变成同类子问题。
步骤讲解
选择基准值
在当前区间中选一个元素作为基准，用它划分左右两侧。
做 partition
遍历区间，把小于等于基准值的元素交换到左侧，最后把基准值放到中间。
递归排序左右子区间
基准值归位后，分别递归处理它左边和右边的区间。
易错点
partition 后忘记递归边界
会重复处理已归位的基准值，甚至导致死循环。
把平均复杂度当成最坏复杂度
快速排序平均是 O(n log n)，但最坏情况会退化到 O(n^2)。
交换逻辑写乱导致 partition 失败
一旦左右边界维护错误，基准值两侧就不再有序分区。
复杂度与适用判断
额外提醒
- partition 是快速排序真正的核心动作。
其他语言 / 其他解法
heap-sort
算法思路：
堆排序是一种基于比较的排序算法，它利用堆这种数据结构来进行排序。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
核心思想：
- 构建最大堆：将待排序数组转换为最大堆结构，堆顶元素为最大值
- 交换堆顶与末尾元素：将堆顶元素（最大值）与数组末尾元素交换，将最大值固定在数组末尾
- 调整堆结构：将剩余的n-1个元素重新调整为最大堆
- 重复步骤2和3，直到整个数组有序
堆调整过程：
- 从最后一个非叶子节点开始，自下而上、自右向左进行调整
- 对于每个节点，比较其与左右子节点的大小，将最大元素交换到父节点位置
- 递归调整受影响的子树
复杂度分析：
- 时间复杂度：O(n log n)，其中O(n)用于构建堆，O(n log n)用于n-1次堆调整
- 空间复杂度：O(1)，原地排序，只需要常数级别的额外空间
heap-sort
算法思路：
堆排序是一种基于比较的排序算法，它利用堆这种数据结构来进行排序。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
核心思想：
堆调整过程：
复杂度分析：
- 构建最大堆：将待排序数组转换为最大堆结构，堆顶元素为最大值
- 交换堆顶与末尾元素：将堆顶元素（最大值）与数组末尾元素交换，将最大值固定在数组末尾
- 调整堆结构：将剩余的n-1个元素重新调整为最大堆
- 重复步骤2和3，直到整个数组有序
- 从最后一个非叶子节点开始，自下而上、自右向左进行调整
- 对于每个节点，比较其与左右子节点的大小，将最大元素交换到父节点位置
- 递归调整受影响的子树
- 时间复杂度：O(n log n)，其中O(n)用于构建堆，O(n log n)用于n-1次堆调整
- 空间复杂度：O(1)，原地排序，只需要常数级别的额外空间
class Solution {
public int[] sortArray(int[] nums) {
heapSort(nums);
return nums;
}
public void heapSort(int[] nums) {
int len = nums.length - 1;
buildMaxHeap(nums, len);
for (int i = len; i >= 1; --i) {
swap(nums, i, 0);
len -= 1;
maxHeapify(nums, 0, len);
}
}
public void buildMaxHeap(int[] nums, int len) {
for (int i = len / 2; i >= 0; --i) {
maxHeapify(nums, i, len);
}
}
public void maxHeapify(int[] nums, int i, int len) {
for (; (i << 1) + 1 <= len;) {
int lson = (i << 1) + 1;
int rson = (i << 1) + 2;
int large;
if (lson <= len && nums[lson] > nums[i]) {
large = lson;
} else {
large = i;
}
if (rson <= len && nums[rson] > nums[large]) {
large = rson;
}
if (large != i) {
swap(nums, i, large);
i = large;
} else {
break;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}动画演示
如果你还没完全看懂，可以展开动画演示。
quick-sort动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
quick-sort动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
heap-sort动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
heap-sort动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。