LeetCode 912. 排序数组

2026-06-03 HGNULB 约 6 分钟

文章信息 14 个分类 9 个标签

分类

LeetCode CodeTop 中等未解决需复习 10-20 字节跳动美团快手腾讯百度滴滴虾皮作业帮

题目描述

✅ 912. 排序数组

题意分析

给定一个整数数组，返回它升序排列后的结果。题面没有禁止调用语言自带的排序库；但把它作为排序算法练习或面试题时，通常需要手写一个正确且复杂度过关的排序，因此本文实现归并排序。

约束信号有两处。一是元素个数最多五万，$O(n^2)$ 的做法无法通过大规模数据，本文选用最坏 $O(n \log n)$ 的归并排序。二是元素范围为 -5 × 10⁴ 到 5 × 10⁴，在本题中使用计数排序也可行，但它依赖有限值域；面试主解更适合选择不依赖数值范围的通用比较排序。实现时还应主动覆盖大量重复、已有序和逆序输入，避免手写排序在特殊分布下退化或出错。

边界包括只有一个元素、全部元素相同、包含负数、以及输入本来就升序或降序；题目保证数组非空，但手写的模板最好也能安全处理空输入。

解法：归并排序

核心思路

本题需要手写一个在极端输入下仍可靠的排序。选择归并排序：区间按下标对半划分，与元素分布无关，因此即使数组已经有序、逆序或全部相等，递归树高度仍是 $O(\log n)$，不存在朴素快速排序退化为 $O(n^2)$ 的风险。

递归契约是：mergeSort(nums, left, right) 返回后，闭区间 [left, right] 已升序排列，区间外元素不变。分别排好左右两半后，用两个指针线性合并：每次取两段当前较小值，写入临时数组。

合并时的不变量是：临时数组 [left, write) 始终保存两段中已经确定的最小元素，并且有序。相等时优先取左段，能够保持排序稳定。临时数组只在入口申请一次并复用，避免递归过程中反复分配。

解题步骤

创建长度为 $n$ 的临时数组，对 [0, n-1] 执行归并排序。

若 left >= right，区间长度至多为 1，直接返回。

计算中点，递归排好 [left, mid] 与 [mid+1, right]。

双指针比较两个有序区间，把较小值写入临时数组；一侧耗尽后复制另一侧剩余元素。

将临时数组的 [left, right] 复制回原数组。

例如 [5, 2, 3, 1] 先被拆为 [5, 2] 与 [3, 1]，分别得到 [2, 5]、[1, 3]；最终合并时依次取 1、2、3、5，得到升序结果。

代码实现

class Solution {
    public int[] sortArray(int[] nums) {
        int[] temp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1, temp);
        return nums;
    }

    private void mergeSort(int[] nums, int left, int right, int[] temp) {
        if (left >= right) {
            return;
        }

        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid, temp);
        mergeSort(nums, mid + 1, right, temp);
        merge(nums, left, mid, right, temp);
    }

    private void merge(int[] nums, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int write = left;

        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[write++] = nums[i++];
            } else {
                temp[write++] = nums[j++];
            }
        }
        while (i <= mid) {
            temp[write++] = nums[i++];
        }
        while (j <= right) {
            temp[write++] = nums[j++];
        }
        System.arraycopy(temp, left, nums, left, right - left + 1);
    }
}

func sortArray(nums []int) []int {
    temp := make([]int, len(nums))
    mergeSort(nums, 0, len(nums)-1, temp)
    return nums
}

func mergeSort(nums []int, left int, right int, temp []int) {
    if left >= right {
        return
    }

    mid := left + (right-left)/2
    mergeSort(nums, left, mid, temp)
    mergeSort(nums, mid+1, right, temp)
    merge(nums, left, mid, right, temp)
}

func merge(nums []int, left int, mid int, right int, temp []int) {
    i, j, write := left, mid+1, left
    for i <= mid && j <= right {
        if nums[i] <= nums[j] {
            temp[write] = nums[i]
            i++
        } else {
            temp[write] = nums[j]
            j++
        }
        write++
    }
    for i <= mid {
        temp[write] = nums[i]
        i++
        write++
    }
    for j <= right {
        temp[write] = nums[j]
        j++
        write++
    }
    copy(nums[left:right+1], temp[left:right+1])
}

复杂度分析

时间复杂度：最好、平均、最坏均为 $O(n \log n)$。递归共有 $O(\log n)$ 层，每层合并所有区间的总工作量为 $O(n)$。

空间复杂度：$O(n)$。临时数组占 $O(n)$，递归栈占 $O(\log n)$，由前者主导。

关键点总结

对半划分不依赖数据内容，因此最坏时间复杂度有确定的 $O(n \log n)$ 上界。

递归返回时左右区间必须已经有序，线性合并的前提才成立。

相等时先取左侧元素，归并排序才能保持稳定。

临时数组只分配一次；每次只回写当前区间，不能覆盖尚未处理的区域。

面试若选择快速排序，需要额外说明随机基准或三路分区如何避免有序数组和大量重复值导致退化；归并排序则用 $O(n)$ 空间换取稳定的最坏界。

易错点总结

右区间写成 [mid, right]，区间不会缩小，会无限递归；正确起点是 mid + 1。

合并后忘记回写原数组，上层递归仍会读取未排序的数据。

回写整个数组会覆盖其他尚未处理的区间；只能复制 [left, right]。

主循环结束后漏掉某一侧的剩余元素，会造成元素丢失或残留旧值。

比较使用 < 虽不影响数值排序结果，但会破坏相等元素的稳定顺序。

每次递归都新建临时数组会增加分配和回收开销；在入口统一申请即可。

相似题目

题目	难度	考察点
148. 排序链表	中等	链表上的常数空间归并
LCR 077. 排序链表	中等	快慢指针拆分链表
补充题 5. 手撕归并排序	中等	归并模板默写
88. 合并两个有序数组	简单	从后往前原地合并
315. 计算右侧小于当前元素的个数	困难	借合并过程统计逆序对
493. 翻转对	困难	合并前额外双指针计数
215. 数组中的第K个最大元素	中等	分区思想做快速选择