LeetCode 912. 排序数组

约 6 分钟
文章信息 25 个分类 8 个标签
分类
LeetCode CodeTop 中等 未解决 需复习 10-20 腾讯 字节 阿里 美团 拼多多 京东 小米 百度 小红书 快手 滴滴 携程 虾皮 顺丰 招行 深信服 度小满 猿辅导 作业帮
标签
数组 排序 堆（优先队列） 分治 归并排序 桶排序 计数排序 基数排序

题目描述

✅ 912. 排序数组

image-20260928213913070

题意分析

将数组排成非递减顺序，重复元素也要完整保留。数组长度可达 $5\times10^4$，可以采用最坏时间为 $O(n\log n)$ 的归并排序。

两个已有序的数组很容易合并：每次比较它们剩余部分的第一个元素，就能确定下一个最小值。因此先把数组不断分成两半，直到每段只剩一个元素，再逐层合并，就把整体排序转化成了更小的排序问题。

解法：归并排序

核心思路

[!blue]

mergeSort(nums, left, right, temp) 负责排好闭区间 [left, right]。区间长度至多为一时已经有序；否则分为 [left, mid] 和 [mid+1, right]，等两次递归都返回后再合并。

合并时，i、j 分别指向左右两段尚未取出的第一个元素，write 指向临时数组中下一个待写位置。两段内部都有序，所以剩余元素的最小值必在 nums[i]、nums[j] 中；取较小者并移动对应指针，就能让已写入的部分始终有序。某侧耗尽后，另一侧剩余元素本来就有序，直接接到末尾即可。

每个元素恰好取出一次，合并得到的既是原区间的全部元素，又保持有序。单元素区间成立，而两个有序子区间合并后也成立，因此最外层返回时整个数组有序。

temp 在入口申请一次，各次合并复用自己对应的下标范围；只有 [left, right] 被本次填好，所以也只回写这一段。相等时先取左侧元素，能进一步保持相等元素原来的先后顺序。

解题步骤

  1. 创建长度为 $n$ 的临时数组，对 [0, n-1] 执行归并排序。
  2. 若 left >= right，区间长度至多为 1，直接返回。
  3. 计算中点，递归排好 [left, mid] 与 [mid+1, right]。
  4. 双指针比较两个有序区间，把较小值写入临时数组；一侧耗尽后复制另一侧剩余元素。
  5. 将临时数组的 [left, right] 复制回原数组。

代码实现

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)$，由前者主导。

关键点总结

[!green]

  • 对半划分不依赖数据内容，因此最坏时间复杂度有确定的 $O(n \log n)$ 上界。
  • 递归返回时左右区间必须已经有序，线性合并的前提才成立。
  • 相等时先取左侧元素，归并排序才能保持稳定。
  • 临时数组只分配一次；每次只回写当前区间，不能覆盖尚未处理的区域。

易错点总结

[!yellow]

  • 右区间写成 [mid, right]，区间不会缩小，会无限递归；正确起点是 mid + 1。
  • 合并后忘记回写原数组，上层递归仍会读取未排序的数据。
  • 回写整个数组会覆盖其他尚未处理的区间；只能复制 [left, right]。
  • 主循环结束后漏掉某一侧的剩余元素，会造成元素丢失或残留旧值。
  • 比较使用 < 虽不影响数值排序结果，但会破坏相等元素的稳定顺序。
  • 每次递归都新建临时数组会增加分配和回收开销；在入口统一申请即可。
  • 元素全相等、已排序或逆序时，都按同样的区间划分处理；负数也只参与大小比较，不需要额外分支。

相似题目

题目 难度 关联与区别
148. 排序链表 中等 数组与链表都可归并排序，但链表切分和合并用指针，数组可按下标直接分区。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/03329404
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！