排序数组 图解题解
这道题到底在问什么
- 输入
- nums=[5,2,3,1]
- 输出
- [1,2,3,5] （普通乱序）
- 输入
- nums=[5,1,1,2,0,0]
- 输出
- [0,0,1,1,2,5] （含重复元素，重复值要完整保留并按升序排列）
- 输入
- nums=[1]
- 输出
- [1] （单元素直接返回）
最优解：一步一步想明白
- 3记住「拆到单个、再两两合并」这套，下面每一帧都在套它。
- 4开局：柱子高度就是数值，下方数字是下标。整段都还是乱的，先把它从正中间切开。
- 5第一刀切在下标 3：左半 [5, 2, 3]，右半 [1, 6, 4]。两半各自再递归去排。
- 6先看左半（其余灰掉）：[5, 2, 3] 再切成 [5] 和 [2, 3]，一直拆到每段只剩一个数：单个数天然有序，递归就到底了。
- 7拆到极致：六个数变成六段单元素，每段都已经有序。接下来是关键，两两合并，把小有序段拼成大有序段。
- 8要合并的两段：左 [2]、右 [3]，都已有序。两边各放一个指针从头开始，每次挑更小的那个先放进结果。
- 9两个指针处比一比：左 2 对 右 3。左边更小（或相等），先放 2，左指针前移。
- 10挑完两边，这一段合成 [2, 3]，整段已升序（绿色）。这段就排好了，回到上一层继续和别的段合并。
- 11要合并的两段：左 [5]、右 [2, 3]，都已有序。两边各放一个指针从头开始，每次挑更小的那个先放进结果。
- 12两个指针处比一比：左 5 对 右 2。右边更小，先放 2，右指针前移。
- 13两个指针处比一比：左 5 对 右 3。右边更小，先放 3，右指针前移。
- 14挑完两边，这一段合成 [2, 3, 5]，整段已升序（绿色）。这段就排好了，回到上一层继续和别的段合并。
- 15要合并的两段：左 [6]、右 [4]，都已有序。两边各放一个指针从头开始，每次挑更小的那个先放进结果。
- 16两个指针处比一比：左 6 对 右 4。右边更小，先放 4，右指针前移。
- 17挑完两边，这一段合成 [4, 6]，整段已升序（绿色）。这段就排好了，回到上一层继续和别的段合并。
- 18要合并的两段：左 [1]、右 [4, 6]，都已有序。两边各放一个指针从头开始，每次挑更小的那个先放进结果。
- 19两个指针处比一比：左 1 对 右 4。左边更小（或相等），先放 1，左指针前移。
- 20挑完两边，这一段合成 [1, 4, 6]，整段已升序（绿色）。这段就排好了，回到上一层继续和别的段合并。
- 21要合并的两段：左 [2, 3, 5]、右 [1, 4, 6]，都已有序。两边各放一个指针从头开始，每次挑更小的那个先放进结果。
- 22两个指针处比一比：左 2 对 右 1。右边更小，先放 1，右指针前移。
- 23两个指针处比一比：左 2 对 右 4。左边更小（或相等），先放 2，左指针前移。
- 24两个指针处比一比：左 3 对 右 4。左边更小（或相等），先放 3，左指针前移。
- 25两个指针处比一比：左 5 对 右 4。右边更小，先放 4，右指针前移。
- 26两个指针处比一比：左 5 对 右 6。左边更小（或相等），先放 5，左指针前移。
- 27挑完两边，这一段合成 [1, 2, 3, 4, 5, 6]，它就是整个数组，全部升序（绿色），最终合并完成，排序结束。
- 28最后一次合并把左右两大段拼成整段：[1, 2, 3, 4, 5, 6]，全部升序（全绿）。柱子从矮到高一字排开，排序完成。
⚠️ 容易写错的地方
✗ 错：只会冒泡/选择排序 O(n²)
✓ 对：用归并/快排达到 O(n log n)
n 到 5*10^4 时 O(n²) 约 25 亿次操作会超时，必须用 n log n 的排序
✗ 错：以为合并时相等必须先放右边才对
✓ 对：本题只要升序，相等时先放左或先放右最终数值结果都正确
若要写稳定归并（保留原相对次序），相等时优先放左；但 lc912 只看升序结果，左右都不影响最终数组
✗ 错：忘了处理负数
✓ 对：比较用整数大小，负数同样适用
题目数值范围含负数，按数值比较即可，无需特殊处理
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
nums.sort()
return numsC++
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums;
}
};Java
import java.util.*;
class Solution {
public int[] sortArray(int[] nums) {
Arrays.sort(nums);
return nums;
}
}复杂度
时间
O(n log n)
共 log n 层，每层合并要扫过全部 n 个元素，相乘即 n log n
空间
O(n)
归并合并时需要一个临时数组暂存；递归栈深 O(log n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 排序数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
归并排序和快速排序怎么选？+
归并排序最坏也是 O(n log n)、且稳定，但需要 O(n) 额外空间；快速排序平均 O(n log n)、原地（O(log n) 栈），但最坏会退化到 O(n²)（可用随机化或三数取中缓解）、且不稳定。要稳定或要最坏保证选归并，要省空间且数据随机选快排。
为什么内置排序（如 Java 的 Arrays.sort）通常足够，还要会手写？+
内置排序底层就是 O(n log n) 的成熟实现（TimSort、内省排序等），日常直接用最省事。但面试常要求手写归并或快排来考查分治思想、边界处理和复杂度分析，所以这套手写实现必须会。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 排序数组 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。