912. 排序数组

1. 题目描述

给定一个整数数组 nums，请将数组按升序排列，并返回排序后的数组。

题目要求不能只依赖内置排序来糊过去，面试中通常希望能手写一个时间复杂度稳定的排序算法。

示例：

输入：nums = [5, 2, 3, 1]
输出：[1, 2, 3, 5]
解释：把数组中的元素从小到大排列。

示例 2：

输入：nums = [5, 1, 1, 2, 0, 0]
输出：[0, 0, 1, 1, 2, 5]
解释：重复元素也要保留，并按照升序放到正确位置。

2. 题型判断

本题是典型的数组排序题。

可以选择快速排序、归并排序、堆排序等 O(n log n) 级别算法。这里优先使用归并排序，因为它的最坏时间复杂度也是 O(n log n)，不会像普通快排那样在极端输入下退化到 O(n^2)。

归并排序的核心是分治：

先把数组不断拆成更小的区间。
当区间长度为 1 时，它天然有序。
再把两个已经有序的子区间合并成一个更大的有序区间。

3. 核心思路

使用自顶向下的归并排序。

对区间 [left, right] 来说：

如果 left >= right，说明区间里最多只有一个元素，已经有序。
取中点 mid，递归排序左半区间 [left, mid]。
递归排序右半区间 [mid + 1, right]。
使用双指针合并两个有序区间。

合并时维护两个指针：

i 指向左半区间当前还没有合并的元素。
j 指向右半区间当前还没有合并的元素。

每次比较 nums[i] 和 nums[j]，把较小的元素放入临时数组 temp。当某一边用完后，把另一边剩余元素全部追加进去，最后再把 temp 覆盖回原数组的 [left, right] 区间。

4. 示例步骤图解

以 nums = [5, 2, 3, 1] 为例。

拆分过程

[5, 2, 3, 1]
      |
      +-- [5, 2]
      |      |
      |      +-- [5]
      |      +-- [2]
      |
      +-- [3, 1]
             |
             +-- [3]
             +-- [1]

长度为 1 的区间已经有序，接下来开始向上合并。

合并过程

步骤	左有序区间	右有序区间	合并结果
1	`[5]`	`[2]`	`[2, 5]`
2	`[3]`	`[1]`	`[1, 3]`
3	`[2, 5]`	`[1, 3]`	`[1, 2, 3, 5]`

第 3 步合并细节：

比较	选择	temp
`2` 和 `1`	选择 `1`	`[1]`
`2` 和 `3`	选择 `2`	`[1, 2]`
`5` 和 `3`	选择 `3`	`[1, 2, 3]`
左侧剩余 `5`	追加 `5`	`[1, 2, 3, 5]`

最终数组变为 [1, 2, 3, 5]。

5. 变量与区间含义

本题使用闭区间 [left, right]。

left：当前排序区间的左边界。
right：当前排序区间的右边界。
mid：当前区间的中点，用来把区间拆成左右两半。
i：合并时左半区间 [left, mid] 的扫描指针。
j：合并时右半区间 [mid + 1, right] 的扫描指针。
temp：临时数组，保存当前区间合并后的升序结果。
k：把 temp 写回 nums 时使用的下标。

递归函数 mergeSort(nums, left, right) 的含义是：把 nums 的闭区间 [left, right] 排成升序。

6. 推进规则

拆分规则

如果 left >= right，区间长度小于等于 1，直接返回。
否则取 mid = left + Math.floor((right - left) / 2)。
先排序 [left, mid]，再排序 [mid + 1, right]。

合并规则

合并两个已经有序的区间 [left, mid] 和 [mid + 1, right]：

如果 nums[i] <= nums[j]，把 nums[i] 放入 temp，然后 i++。
如果 nums[i] > nums[j]，把 nums[j] 放入 temp，然后 j++。
如果左半区间还有剩余元素，依次追加。
如果右半区间还有剩余元素，依次追加。
最后把 temp 写回 nums[left] 到 nums[right]。

这里使用 nums[i] <= nums[j] 时优先放左边元素，可以让归并排序保持稳定性。虽然本题只返回数值数组，稳定性不是必须的，但这是一个好习惯。

7. 边界条件与易错点

空数组或单元素数组本身已经有序，递归会自然返回。
mid 要写成 left + Math.floor((right - left) / 2)，避免在其他语言中出现整数溢出。
合并前必须保证左右两段已经分别有序，所以要先递归排序，再合并。
合并后要把 temp 写回原数组对应区间，否则上一层递归拿到的仍然是旧顺序。
写回时下标要从 left 开始，而不是从 0 开始覆盖。
普通快速排序平均复杂度是 O(n log n)，但最坏会退化；本题数据可能比较刁钻，归并排序更稳。

8. 代码实现

归并排序特点：

分治思想很清晰，先拆分，再合并。
时间复杂度稳定，最好、平均、最坏都是 O(n log n)。
需要额外临时数组，空间复杂度是 O(n)。
是稳定排序，相等元素的相对顺序不会被改变。
很适合作为本题主解，因为它不怕数组有序、逆序、重复元素多等极端情况。

归并排序图解：

nums = [5, 2, 3, 1]

先拆分：
[5, 2, 3, 1]
   /       \
[5, 2]   [3, 1]
 /  \     /  \
[5] [2] [3] [1]

再合并：
[5] + [2]       => [2, 5]
[3] + [1]       => [1, 3]
[2, 5] + [1, 3] => [1, 2, 3, 5]

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  mergeSort(nums, 0, nums.length - 1);
  return nums;
};

function mergeSort(nums, left, right) {
  // 闭区间 [left, right] 中最多只有一个元素时，天然有序。
  if (left >= right) {
    return;
  }

  const mid = left + Math.floor((right - left) / 2);

  // 先分别排好左右两半。
  mergeSort(nums, left, mid);
  mergeSort(nums, mid + 1, right);

  // 再把两个有序区间合并成一个有序区间。
  merge(nums, left, mid, right);
}

function merge(nums, left, mid, right) {
  const temp = [];
  let i = left;
  let j = mid + 1;

  // 两边都还有元素时，每次取更小的那个。
  while (i <= mid && j <= right) {
    if (nums[i] <= nums[j]) {
      temp.push(nums[i]);
      i++;
    } else {
      temp.push(nums[j]);
      j++;
    }
  }

  // 左半区间如果还有剩余，直接追加。
  while (i <= mid) {
    temp.push(nums[i]);
    i++;
  }

  // 右半区间如果还有剩余，直接追加。
  while (j <= right) {
    temp.push(nums[j]);
    j++;
  }

  // 把合并结果写回原数组的 [left, right] 区间。
  for (let k = 0; k < temp.length; k++) {
    nums[left + k] = temp[k];
  }
}

9. 复杂度分析

时间复杂度：O(n log n)。
- 每一层合并会扫描全部 n 个元素。
- 递归拆分一共有 log n 层。
空间复杂度：O(n)。
- 合并过程需要临时数组。
- 递归调用栈需要 O(log n)，整体主导空间是临时数组的 O(n)。

10. 其他解法

解法一：随机快速排序

快速排序也很常见。它通过 partition 把数组分成两部分：

小于等于 pivot 的元素放左侧。
大于 pivot 的元素放右侧。

然后递归排序左右两边。

为了降低退化概率，最好随机选择 pivot。不过即使随机化，理论最坏时间复杂度仍然是 O(n^2)。

快速排序特点：

原地排序，不需要像归并排序一样开 O(n) 的辅助数组。
平均时间复杂度是 O(n log n)，实际运行通常很快。
最坏时间复杂度是 O(n^2)，例如每次 pivot 都选到极端位置。
不稳定，相同元素可能因为交换而改变相对顺序。
面试中常考 partition 分区逻辑，要特别注意左右边界和 pivot 归位。

快速排序图解：

以 nums = [5, 2, 3, 1]，假设第一次随机到的 pivot = 3 为例：

原数组：
[5, 2, 3, 1]

按 pivot = 3 分区：
[2, 1]  3  [5]
 小于等于    大于

继续递归处理左右两侧：
[2, 1] => [1, 2]
[5]    => [5]

拼回整体：
[1, 2, 3, 5]

var sortArray = function (nums) {
  quickSort(nums, 0, nums.length - 1);
  return nums;
};

function quickSort(nums, left, right) {
  if (left >= right) {
    return;
  }

  const p = partition(nums, left, right);
  quickSort(nums, left, p - 1);
  quickSort(nums, p + 1, right);
}

function partition(nums, left, right) {
  const pivotIndex = left + Math.floor(Math.random() * (right - left + 1));
  [nums[pivotIndex], nums[right]] = [nums[right], nums[pivotIndex]];

  const pivot = nums[right];
  let storeIndex = left;

  for (let i = left; i < right; i++) {
    if (nums[i] <= pivot) {
      [nums[storeIndex], nums[i]] = [nums[i], nums[storeIndex]];
      storeIndex++;
    }
  }

  [nums[storeIndex], nums[right]] = [nums[right], nums[storeIndex]];
  return storeIndex;
}

解法二：堆排序

堆排序也能做到原地 O(n log n)，额外空间是 O(1)。它先建立大顶堆，然后反复把堆顶最大值交换到数组末尾，再缩小堆的有效范围。

堆排序特点：

原地排序，额外空间复杂度是 O(1)。
最好、平均、最坏时间复杂度都是 O(n log n)。
不稳定，因为堆顶和末尾交换可能打乱相同元素的相对顺序。
不依赖随机化，复杂度比快排更稳。
代码重点在 heapify，要理解父节点和左右孩子的下标关系。

堆排序图解：

以 nums = [5, 2, 3, 1] 为例，先把数组看成完全二叉树：

数组下标： 0  1  2  3
数组内容：[5, 2, 3, 1]

        5
      /   \
     2     3
    /
   1

建立大顶堆后，堆顶就是当前最大值。每轮把堆顶交换到末尾，再对剩余部分重新调整：

轮次	当前堆区间	交换堆顶到末尾后	已排序区间
初始	`[5, 2, 3, 1]`	-	`[]`
1	`[5, 2, 3, 1]`	`[3, 2, 1, 5]`	`[5]`
2	`[3, 2, 1]`	`[2, 1, 3, 5]`	`[3, 5]`
3	`[2, 1]`	`[1, 2, 3, 5]`	`[2, 3, 5]`

var sortArray = function (nums) {
  const n = nums.length;

  // 建立大顶堆。
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(nums, n, i);
  }

  // 每次把当前最大值放到末尾。
  for (let end = n - 1; end > 0; end--) {
    [nums[0], nums[end]] = [nums[end], nums[0]];
    heapify(nums, end, 0);
  }

  return nums;
};

function heapify(nums, heapSize, root) {
  let largest = root;
  const left = root * 2 + 1;
  const right = root * 2 + 2;

  if (left < heapSize && nums[left] > nums[largest]) {
    largest = left;
  }

  if (right < heapSize && nums[right] > nums[largest]) {
    largest = right;
  }

  if (largest !== root) {
    [nums[root], nums[largest]] = [nums[largest], nums[root]];
    heapify(nums, heapSize, largest);
  }
}

解法三：计数排序

如果已知数组元素范围不大，可以使用计数排序。

LeetCode 912 的常见约束是 -5 * 10^4 <= nums[i] <= 5 * 10^4，数值范围大约是 10^5，可以开一个计数数组记录每个数字出现了多少次，然后按从小到大的顺序写回 nums。

计数排序不是基于比较的排序。它的时间复杂度和数组长度、数值范围有关。

计数排序特点：

不是比较排序，而是统计每个值出现的次数。
当数值范围 k 不大时，时间复杂度可以做到 O(n + k)。
需要额外计数数组，空间复杂度是 O(k)。
适合整数排序，不适合值域很大或小数、字符串等场景。
如果需要处理负数，要用 num - min 做偏移，不能直接把数字当数组下标。

计数排序图解：

以 nums = [5, 1, 1, 2, 0, 0] 为例：

min = 0
max = 5

统计每个值出现次数：
值：   0  1  2  3  4  5
次数： 2  2  1  0  0  1

按照次数从小到大写回：
0 出现 2 次 => [0, 0]
1 出现 2 次 => [0, 0, 1, 1]
2 出现 1 次 => [0, 0, 1, 1, 2]
5 出现 1 次 => [0, 0, 1, 1, 2, 5]

var sortArray = function (nums) {
  if (nums.length <= 1) {
    return nums;
  }

  let min = nums[0];
  let max = nums[0];

  for (const num of nums) {
    min = Math.min(min, num);
    max = Math.max(max, num);
  }

  const count = new Array(max - min + 1).fill(0);

  for (const num of nums) {
    count[num - min]++;
  }

  let index = 0;

  for (let i = 0; i < count.length; i++) {
    const value = i + min;

    while (count[i] > 0) {
      nums[index] = value;
      index++;
      count[i]--;
    }
  }

  return nums;
};

复杂度：

时间复杂度：O(n + k)，k = max - min + 1。
空间复杂度：O(k)。

解法四：插入排序

插入排序会维护一个已经有序的前缀区间。每次取出当前位置 i 的元素，把它插入到左侧有序区间中的正确位置。

它适合小规模数组，或者数组本身已经接近有序的场景。对于 LeetCode 912 这种大数据排序题，最坏 O(n^2) 通常不够稳。

插入排序特点：

维护左侧有序区间，把当前元素插入到正确位置。
对接近有序的数组很友好，最好时间复杂度可以到 O(n)。
平均和最坏时间复杂度是 O(n^2)，不适合大规模乱序数组。
原地排序，空间复杂度是 O(1)。
稳定排序，因为相等元素不会跨过彼此。

插入排序图解：

以 nums = [5, 2, 3, 1] 为例，左侧灰色含义是“已经有序的前缀区间”：

初始：
[5 | 2, 3, 1]

i = 1，插入 2：
[2, 5 | 3, 1]

i = 2，插入 3：
[2, 3, 5 | 1]

i = 3，插入 1：
[1, 2, 3, 5]

var sortArray = function (nums) {
  for (let i = 1; i < nums.length; i++) {
    const current = nums[i];
    let j = i - 1;

    // 把比 current 大的元素整体右移。
    while (j >= 0 && nums[j] > current) {
      nums[j + 1] = nums[j];
      j--;
    }

    nums[j + 1] = current;
  }

  return nums;
};

复杂度：

时间复杂度：平均和最坏 O(n^2)，最好 O(n)。
空间复杂度：O(1)。
稳定性：稳定。

解法五：选择排序

选择排序每一轮从未排序区间中找到最小值，把它交换到当前轮的起始位置。

它的实现很直观，但无论数组是否接近有序，都要做大量比较，因此时间复杂度固定是 O(n^2)。

选择排序特点：

每一轮从未排序区间里选出最小值，放到当前起点。
交换次数少，最多交换 n - 1 次。
比较次数固定很多，最好、平均、最坏时间复杂度都是 O(n^2)。
原地排序，空间复杂度是 O(1)。
通常不稳定，因为最小值交换到前面时可能跨过相同元素。

选择排序图解：

以 nums = [5, 2, 3, 1] 为例，每一轮选出未排序区间的最小值：

初始：
[5, 2, 3, 1]

第 1 轮：未排序区间 [5, 2, 3, 1]，最小值是 1，交换到下标 0
[1 | 2, 3, 5]

第 2 轮：未排序区间 [2, 3, 5]，最小值是 2，位置不变
[1, 2 | 3, 5]

第 3 轮：未排序区间 [3, 5]，最小值是 3，位置不变
[1, 2, 3 | 5]

最终：
[1, 2, 3, 5]

var sortArray = function (nums) {
  const n = nums.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < n; j++) {
      if (nums[j] < nums[minIndex]) {
        minIndex = j;
      }
    }

    if (minIndex !== i) {
      [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
    }
  }

  return nums;
};

复杂度：

时间复杂度：O(n^2)。
空间复杂度：O(1)。
稳定性：通常不稳定，因为交换可能改变相同元素的相对顺序。

解法六：冒泡排序

冒泡排序每一轮比较相邻元素，如果顺序错误就交换。每一轮结束后，当前未排序区间中的最大值会被“冒泡”到末尾。

可以用 swapped 做提前结束优化：如果某一轮没有发生交换，说明数组已经有序。

冒泡排序特点：

每次只比较相邻元素，顺序不对就交换。
每一轮会把当前未排序区间的最大值放到末尾。
加上 swapped 后，数组已经有序时最好时间复杂度是 O(n)。
平均和最坏时间复杂度是 O(n^2)，不适合大规模数组。
稳定排序，因为相等元素不会发生交换。

冒泡排序图解：

以 nums = [5, 2, 3, 1] 为例，每轮把当前最大值交换到未排序区间末尾：

第 1 轮：
[5, 2, 3, 1]
 5 > 2，交换 => [2, 5, 3, 1]
 5 > 3，交换 => [2, 3, 5, 1]
 5 > 1，交换 => [2, 3, 1 | 5]

第 2 轮：
[2, 3, 1 | 5]
 2 <= 3，不交换
 3 > 1，交换 => [2, 1 | 3, 5]

第 3 轮：
[2, 1 | 3, 5]
 2 > 1，交换 => [1 | 2, 3, 5]

var sortArray = function (nums) {
  const n = nums.length;

  for (let end = n - 1; end > 0; end--) {
    let swapped = false;

    for (let i = 0; i < end; i++) {
      if (nums[i] > nums[i + 1]) {
        [nums[i], nums[i + 1]] = [nums[i + 1], nums[i]];
        swapped = true;
      }
    }

    if (!swapped) {
      break;
    }
  }

  return nums;
};

复杂度：

时间复杂度：平均和最坏 O(n^2)，最好 O(n)。
空间复杂度：O(1)。
稳定性：稳定。

解法七：希尔排序

希尔排序可以看作插入排序的优化版。它先按较大的间隔 gap 分组做插入排序，让元素更快接近最终位置；再逐步缩小 gap，直到 gap = 1 时完成最后一次插入排序。

它的代码不复杂，实际表现通常比普通插入排序好，但复杂度分析和 gap 序列有关，不如归并、堆排那样稳定清晰。

希尔排序特点：

是插入排序的改进版，通过较大的 gap 先让元素快速靠近最终位置。
原地排序，空间复杂度是 O(1)。
实际表现通常比普通插入排序好。
时间复杂度和 gap 序列有关，不像归并、堆排那样容易给出统一结论。
不稳定，因为相同元素可能在不同 gap 分组移动时改变相对顺序。

希尔排序图解：

以 nums = [5, 2, 3, 1] 为例，先用较大的 gap 分组，再缩小到普通插入排序：

初始：
[5, 2, 3, 1]

gap = 2，分成两组：
下标 0, 2： [5, 3] => [3, 5]
下标 1, 3： [2, 1] => [1, 2]

数组变为：
[3, 1, 5, 2]

gap = 1，对整个数组做插入排序：
[1, 2, 3, 5]

var sortArray = function (nums) {
  const n = nums.length;

  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < n; i++) {
      const current = nums[i];
      let j = i - gap;

      while (j >= 0 && nums[j] > current) {
        nums[j + gap] = nums[j];
        j -= gap;
      }

      nums[j + gap] = current;
    }
  }

  return nums;
};

复杂度：

时间复杂度：和 gap 序列有关，常见写法最坏可能到 O(n^2)。
空间复杂度：O(1)。
稳定性：不稳定。

排序算法选择总结

算法	平均时间	最坏时间	额外空间	稳定性	适用场景
归并排序	`O(n log n)`	`O(n log n)`	`O(n)`	稳定	追求稳定复杂度，适合本题主解
随机快排	`O(n log n)`	`O(n^2)`	`O(log n)`	不稳定	实战常用，平均性能好
堆排序	`O(n log n)`	`O(n log n)`	`O(1)`	不稳定	需要原地排序且保证最坏复杂度
计数排序	`O(n + k)`	`O(n + k)`	`O(k)`	可稳定	整数范围较小时很快
插入排序	`O(n^2)`	`O(n^2)`	`O(1)`	稳定	小数组或接近有序数组
选择排序	`O(n^2)`	`O(n^2)`	`O(1)`	不稳定	教学理解，不适合大数据
冒泡排序	`O(n^2)`	`O(n^2)`	`O(1)`	稳定	教学理解，不适合大数据
希尔排序	取决于 `gap`	取决于 `gap`	`O(1)`	不稳定	插入排序的进阶优化

#912. 排序数组

#1. 题目描述

#2. 题型判断

#3. 核心思路

#4. 示例步骤图解

#拆分过程

#合并过程

#5. 变量与区间含义

#6. 推进规则

#拆分规则

#合并规则

#7. 边界条件与易错点

#8. 代码实现

#9. 复杂度分析

#10. 其他解法

#解法一：随机快速排序

#解法二：堆排序

#解法三：计数排序

#解法四：插入排序

#解法五：选择排序

#解法六：冒泡排序

#解法七：希尔排序

#排序算法选择总结

912. 排序数组

1. 题目描述

2. 题型判断

3. 核心思路

4. 示例步骤图解

拆分过程

合并过程

5. 变量与区间含义

6. 推进规则

拆分规则

合并规则

7. 边界条件与易错点

8. 代码实现

9. 复杂度分析

10. 其他解法

解法一：随机快速排序

解法二：堆排序

解法三：计数排序

解法四：插入排序

解法五：选择排序

解法六：冒泡排序

解法七：希尔排序

排序算法选择总结