冒泡排序

冒泡排序（Bubble Sort）是一种 交换类 的基础排序算法，重复遍历待排序数组，依次 比较相邻两个元素，若顺序错误则交换二者，每一轮遍历都会将当前 未排序部分 中最大（或最小）的元素 “冒泡” 到末尾。

交换类排序算法

通过 比较并交换元素位置 来实现排序，主要操作是相邻或远距离的元素互换。

典型算法

  • 冒泡排序：相邻元素两两比较，大值逐轮"冒泡"到末尾。
  • 快速排序：选定基准值，通过交换将序列分为左右两部分，递归处理。

核心思想

冒泡排序的核心思想是 相邻元素两两比较，通过不断交换将最值逐位后移。

每一轮从前往后遍历，比较每一对相邻元素，若前者大于后者则交换。这个过程中，较大的元素就像气泡一样，一步步 “冒泡” 到当前未排序区间的末尾。

每完成一轮，末尾就多一个已排好的最大值，下一轮比较范围缩短一位，若某轮无交换则提前结束。

实现过程

以升序排序为例：

进行一轮循环，每次循环都找到 未排序部分 的最大元素并交换到末尾，只需要查找 n-1 次就能完成排序（最后一个元素不需要排序）。

1
2
3
for (let i = 0; i < n - 1; i++) {
  // ... 找到未排序部分的最大元素并交换到末尾 ...
}

变量 i 从 0 开始，代表已完成的循环次数，可用于计算 未排序部分 的长度。

循环体通过 冒泡 实现排序：进行一轮循环，每次循环比较当前元素和 下一个元素，把较大的元素 交换 到下一个位置。循环体只对未排序部分进行排序，因此循环体内部的循环次数为 n-1-i（每轮结束后末尾 i 个元素已有序）。

已排序部分置于序列末尾，因此变量 j 从 0 开始。

1
2
3
4
5
for (let j = 0; j < n - 1 - i; j++) {
  if (arr[j] > arr[j + 1]) {
    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
  }
}

[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] 是 JS 数组解构赋值的写法，先创建一个临时数组，再解构赋值给 arr[j] 和 arr[j + 1]。

完整代码

1
2
3
4
5
6
7
8
9
10
11
function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

排序完成后 返回原数组，可以支持链式调用：const result = bubbleSort([5,2,4]).join('-')

复杂度

时间复杂度

  1. 最好情况（数组完全有序）

    代码依然会完整跑完两层循环，需要执行 n(n−1)2\dfrac{n(n - 1)}{2} 次比较。

    时间复杂度：O(n2)O(n^2)

  2. 最坏情况（数组完全逆序）

    每一次比较都要执行交换，比较次数同样是 n(n−1)2\dfrac{n(n - 1)}{2} 次。

    时间复杂度：O(n2)O(n^2)

  3. 平均情况

    随机无序数组，比较次数的期望值是平方级别。

    时间复杂度：O(n2)O(n^2)

空间复杂度

仅用到常量级别的临时变量，没有申请随 nn 增大而增长的额外存储空间，属于 原地排序。

空间复杂度：O(1)O(1)

细节优化

1. 提前终止有序数组

优化点
如果数组已经有序，循环仍然会执行完所有轮次，浪费性能。

如果某个轮次 没有发生交换，代表 未排序部分 已经有序，直接 break 退出。

  • 增加 swapped 变量，记录当前轮次是否发生过交换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false; // 标志位
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // 没有交换，提前退出
  }
  return arr;
}

最好情况：已经有序的数组，一轮遍历结束后直接退出，时间复杂度为 O(n)O(n)。

2. 记录最后交换位置

优化点
内层循环的长度每次 -1，导致末尾已经有序的部分会被重复比较。

每一轮 最后发生交换的位置 之后的元素已经有序，下一轮只需遍历到这个位置。

  • 增加 lastSwapIndex 变量，作为内层循环的右边界。
  • 增加 newLastSwapIndex 变量，记录当前轮次最后发生交换的位置。

内层循环的长度不再固定用 n-1-i，而是根据上一轮最后发生交换的位置 动态更新右边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function bubbleSort(arr) {
  const n = arr.length;
  let lastSwapIndex = n - 1; // 内层循环的右边界

  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    let newLastSwapIndex = 0; // 记录当前轮次最后发生交换的位置

    for (let j = 0; j < lastSwapIndex; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
        newLastSwapIndex = j;
      }
    }

    if (!swapped) break;
    lastSwapIndex = newLastSwapIndex; // 缩小下一轮的范围
  }
  return arr;
}

newLastSwapIndex 的值是交换位置的 左侧，确保它比 lastSwapIndex 小。

算法特性

  1. 稳定性
    冒泡排序是 稳定排序，判断条件只有大于才交换，相等元素的相对先后顺序保持不变。

  2. 原地性
    冒泡排序是 原地排序，只在原数组上进行元素交换，除了几个临时变量外，不需要额外的存储空间。

  3. 自适应性
    经过优化的冒泡排序具有 自适应性，当输入数据已经接近有序或完全有序时，算法可以提前结束。

稳定排序
排序之后，值相等的元素，它们在原数组中的 相对先后顺序 保持不变。

原地排序
排序过程中，不需要额外开辟大量新数组，只使用 常量级别 的临时变量，空间复杂度为 O(1)O(1)。

自适应排序
排序算法的总耗时、比较次数，会受原始数组 有序程度 影响。数组本身越接近有序，算法执行越快。

选择排序

选择排序（Selection Sort）是一种 选择类 的基础排序算法，重复遍历待排序数组，依次在未排序部分中查找 最小（或最大）的元素，将其与 未排序部分的起始位置 交换，每一轮遍历都会将当前未排序部分中最小的元素 “选择” 到最前面。

选择类排序算法

通过 选择极值并放置 来实现排序，每轮在未排序部分选出最小（或最大）元素，直接放到已排序部分的边界。

典型算法

  • 选择排序：每轮选择最小值放到最前面。
  • 堆排序：利用堆数据结构快速获取极值。

核心思想

选择排序的核心思想是 每轮选出最值，放到最前。

外层循环控制轮数（共 n-1 轮，最后一个元素不需要排序），每轮锁定一个待排序的起始位置，内层循环扫描该位置之后的所有元素，记录下最小值（或最大值）的 索引。

扫描结束后，将找到的最值与起始位置元素 交换，这样每轮过后，序列前端就多一个已排序的元素，待排序范围逐步缩小，直至全部有序。

实现过程

以升序排序为例：

进行一轮循环，每次循环都找到 未排序部分 的最小元素，将它交换到未排序区间的开头，只需要查找 n-1 次就能完成排序（最后一个元素不需要排序）。

1
2
3
for (let i = 0; i < n - 1; i++) {
  // ... 找到未排序部分的最小元素并交换到区间开头 ...
}

变量 i 从 0 开始，代表未排序区间的起始下标，i 前面就是已经排好序的部分。

定义最小值索引 minIndex = i，循环体从 未排序区间的第二位 开始遍历，不断更新最小值的索引，遍历完成后，将最小值交换到未排序区间的第一位。

已排序部分置于序列头部，变量 j 从 i + 1 开始向后查找最小值。

1
2
3
4
5
6
7
8
9
let minIndex = i;
for (let j = i + 1; j < n; j++) {
  if (arr[j] < arr[minIndex]) {
    minIndex = j;
  }
}
if (minIndex !== i) {
  [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}

复杂度

时间复杂度

外层循环共执行 n−1n-1 轮：

  • 第 1 轮：比较 n−1n-1 次
  • 第 2 轮：比较 n−2n-2 次
  • ……
  • 第 n−1n-1 轮：比较 11 次

比较次数的总和是 固定值：(n−1)+(n−2)+⋯+1=n(n−1)2(n-1)+(n-2)+\dots+1 = \dfrac{n(n-1)}{2}

最好、平均、最坏的时间复杂度都是 O(n2)O(n^2)

空间复杂度

仅用到常量级别的临时变量，没有申请随 nn 增大而增长的额外存储空间，属于 原地排序。

空间复杂度：O(1)O(1)

细节优化

1. 同时找出最大值和最小值

优化点
基础选择排序每轮需要扫描整个未排序部分，但只标记了两个最值中的一个。

每轮同时找出最小值和最大值，把最小值放左边，最大值放右边，循环次数直接减半。

定义 left 和 right 为未排序部分的左右边界，初始值为 0 和 n-1，整个序列被分为三个部分，左右两侧为已排序序列，中间为未排序序列。通过 while 循环实现 双向选择排序。

如果序列长度为奇数，最终 left 和 right 相等，最后一个元素不需要排序；如果序列长度为偶数，最终 left 会大于 right，需要退出循环。因此循环条件为 while (left < right)。

1
2
3
4
5
6
7
8
9
10
11
function selectionSort(arr) {
  const n = arr.length;
  let left = 0;
  let right = n - 1;

  while (left < right) {
    // ... 排序逻辑 ...
    left++;
    right--;
  }
}

每轮循环，在 [left, right] 范围内找到最小值和最大值的索引，然后将两个最值和未排序部分的 左右边界 交换，完成后 left 和 right 向中间移动。

如果左边界是最大值所在的位置，当最小值和左边界互换后，需要 修正最大值的索引。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function selectionSort(arr) {
  const n = arr.length;
  let left = 0;
  let right = n - 1;

  while (left < right) {
    let minIndex = left;
    let maxIndex = left;

    // 找到最小值和最大值的索引
    for (let i = left + 1; i <= right; i++) {
      if (arr[i] < arr[minIndex]) {
        minIndex = i;
      }
      if (arr[i] > arr[maxIndex]) {
        maxIndex = i;
      }
    }

    // 交换最小值和左边界
    if (minIndex !== left) {
      [arr[left], arr[minIndex]] = [arr[minIndex], arr[left]];
    }

    // 修正最大值的索引
    if (maxIndex === left) {
      maxIndex = minIndex;
    }

    // 交换最大值和右边界
    if (maxIndex !== right) {
      [arr[right], arr[maxIndex]] = [arr[maxIndex], arr[right]];
    }

    left++;
    right--;
  }

  return arr;
}

为什么用 while 代替 for 循环？

for 循环的两种写法：

写法 循环次数 左边界 右边界
for (let i = 0; i < Math.floor(n / 2); i++) n2\dfrac{n}{2} 次 ii n−1−in-1-i
for (let i = 0; i < n - 1; i += 2) n2\dfrac{n}{2} 次 i2\dfrac{i}{2} n−1−i2n-1-\dfrac{i}{2}

双向选择排序需要 left 和 right 每轮各推进 1，所以 i += 2 是不适合的。

1
2
3
4
5
for (let i = 0; i < Math.floor(n / 2); i++) {
  const left = i;
  const right = n - 1 - i;
  // ...
}

for 循环需要通过 i 同时控制循环次数和循环边界，可读性较差。

当循环依赖动态条件时，用 while 更合适。

算法特性

  1. 稳定性
    选择排序是 不稳定排序，因为远距离交换可能改变相等元素的相对顺序。

    数组 [2ₐ, 2ᵦ, 1]，第一轮找到最小值 1，和第一个 2ₐ 交换，数组变成 [1,2ᵦ,2ₐ]。
    原本 2ₐ 在 2ᵦ 前面，交换后反过来，相等元素的相对顺序改变。

  2. 原地性
    选择排序是 原地排序，只在原数组内部做元素交换，使用少量临时变量，不需要额外数组存放数据。

  3. 自适应性
    选择排序无法感知未排序部分是否已经有序，无法提前终止，不具备自适应性。

    if(minIndex === left && maxIndex === right) break;
    这样会把 “最值已在两端” 误认为 “整体已有序”，例如 [1, 3, 2, 4] 没排好序，3 和 2 还是乱的。

插入排序

插入排序（Insertion Sort）是一种 插入类 的基础排序算法，重复遍历待排序数组，依次将当前元素与 已排序部分 逐个比较，找到合适位置插入，逐步扩大有序区间。每一轮遍历都会将当前元素 “插入” 到已排序部分中的正确位置。

插入类排序算法

将未排序的元素 逐个插入到已排序部分 的正确位置，使已排序部分始终保持有序。

典型算法

  • 插入排序：从后往前比较，边比较边后移，找到位置后插入。
  • 希尔排序：插入排序的改进版，通过增量分组实现跨步移动。

核心思想

实现过程

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    let current = arr[i];
    let j = i - 1;

    // 将当前元素与已排序部分从后往前比较
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j]; // 元素后移
      j--;
    }
    arr[j + 1] = current; // 插入到正确位置
  }
  return arr;
}

复杂度

时间复杂度

外层循环共执行 n−1n-1 轮，内层循环将当前元素插入到已排序部分的正确位置：

  • 第 1 轮：最坏比较 11 次，最好比较 11 次
  • 第 2 轮：最坏比较 22 次，最好比较 11 次
  • ……
  • 第 n−1n-1 轮：最坏比较 n−1n-1 次，最好比较 11 次

最坏情况（序列完全逆序）：每次都需要比较并移动所有已排序元素
比较次数：1+2+⋯+(n−1)=n(n−1)21+2+\dots+(n-1)=\dfrac{n(n-1)}{2}

最好情况（序列已有序）：每轮只需比较 11 次即可确定位置
比较次数：1+1+⋯+1=n−11+1+\dots+1=n-1

平均情况：约需比较 n24\dfrac{n^2}{4} 次，时间复杂度仍为 O(n2)O(n^2)

情况 比较次数 移动次数 时间复杂度
最好 n−1n-1 00 O(n)O(n)
最坏 n(n−1)2\dfrac{n(n-1)}{2} n(n−1)2\dfrac{n(n-1)}{2} O(n2)O(n^2)
平均 ≈n24\approx \dfrac{n^2}{4} ≈n24\approx \dfrac{n^2}{4} O(n2)O(n^2)

空间复杂度

仅用到常量级别的临时变量（current 和 j），没有申请随 nn 增大而增长的额外存储空间，属于 原地排序。

空间复杂度：O(1)O(1)

细节优化

算法特性

  1. 稳定性
    插入排序是 稳定排序，插入时从已排序部分末尾向前查找，遇到相等元素时停止移动，将新元素插入到相等元素之后，不会改变相等元素的相对顺序。

  2. 原地性
    插入排序是 原地排序，所有操作都在原数组内部进行，只需要常量级别的临时变量（如 current、j），不需要额外的辅助数组。

  3. 自适应性
    插入排序具备 自适应性，当数据基本有序时，内层循环只需很少的比较就能找到插入位置（甚至只需比较 1 次），时间复杂度可接近 O(n)O(n)。

    数组 [1, 2, 3, 5, 4]，处理最后一个元素 4 时，只需和 5 比较一次即可确定插入位置。

快速排序

快速排序（Quick Sort）是一种 交换类 的高级排序算法，采用 分治 策略：每轮选定一个基准值，通过交换将序列分为两部分 —— 左边都比基准小，右边都比基准大，然后对左右两部分 递归 执行同样操作，每一轮递归都会 将基准元素归位到最终位置。

核心思想

实现过程

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return arr;

  const pivotIndex = partition(arr, left, right);
  quickSort(arr, left, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, right);
  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[right]; // 选最后一个元素为基准
  let i = left - 1; // 指向小于基准区域的末尾

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

  // 将基准放到正确位置
  [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
  return i + 1;
}

复杂度

时间复杂度

快速排序的时间复杂度取决于 基准值的选择 和 数据分布。

最好情况（每次分区都平分序列）：

  • 每次选择的基准都能将序列均匀分成两个大小相等的子序列
  • 递归深度为 log⁡2n\log_2 n，每层比较次数为 nn
  • 时间复杂度：O(nlog⁡n)O(n \log n)

最坏情况（每次分区都极度不平衡）：

  • 基准每次都是序列中的最大或最小元素（如已有序序列选第一个或最后一个为基准）
  • 递归深度为 nn，每层比较次数从 nn 递减到 11
  • 比较次数：n+(n−1)+⋯+1=n(n−1)2n + (n-1) + \dots + 1 = \dfrac{n(n-1)}{2}
  • 时间复杂度：O(n2)O(n^2)

平均情况：

  • 假设基准能大致将序列平分，递归深度约为 log⁡2n\log_2 n
  • 每层比较次数约为 nn
  • 时间复杂度：O(nlog⁡n)O(n \log n)
情况 比较次数 时间复杂度
最好 nlog⁡nn \log n O(nlog⁡n)O(n \log n)
最坏 n(n−1)2\dfrac{n(n-1)}{2} O(n2)O(n^2)
平均 ≈nlog⁡n\approx n \log n O(nlog⁡n)O(n \log n)

空间复杂度

  • 递归调用栈深度取决于递归层数
  • 最好/平均情况：递归深度为 log⁡2n\log_2 n，空间复杂度为 O(log⁡n)O(\log n)
  • 最坏情况：递归深度为 nn，空间复杂度为 O(n)O(n)
  • 仅使用常数级额外空间（原地分区），无额外数组
情况 递归深度 空间复杂度
最好/平均 log⁡2n\log_2 n O(log⁡n)O(\log n)
最坏 nn O(n)O(n)

快速排序在 平均情况 下是实际应用中最快的排序算法，但需要谨慎选择基准以避免最坏情况。

细节优化

算法特性

  1. 稳定性
    快速排序是 不稳定排序，分区操作中，基准元素与指针元素进行远距离交换，可能改变相等元素的相对顺序。

    数组 [3ₐ, 2, 3ᵦ, 1]，选最后一个元素 1 为基准，分区后变为 [1, 2, 3ᵦ, 3ₐ]，两个 3 的相对顺序发生改变。

  2. 原地性
    快速排序是 原地排序，分区操作直接在原数组内部通过交换完成，不需要额外的辅助数组合并，只需常量级的临时变量。

  3. 自适应性
    快速排序 不具备自适应性，快速排序不会因为数据已经有序而减少操作，反而在已有序且基准选择不当（如固定选第一个或最后一个）时性能最差，退化为 O(n2)O(n^2)。

    数组 [1, 2, 3, 4, 5]，选最后一个元素 5 为基准，分区后基准归位，但剩余序列仍为 [1, 2, 3, 4]，问题规模每次只减少 1，递归深度达到 nn，退化为 O(n2)O(n^2)。

归并排序

归并排序是一种 分治类 的排序算法，采用 分治思想，把数组不断对半拆分成两个子数组，直到子数组只有一个元素（天然有序）；再将两个有序子数组合并成一个大的有序数组，逐层向上合并，最终得到完整有序数组。

分治类排序算法

分治类排序算法的核心思想是 分而治之：将复杂的大问题递归 拆分 成若干个规模较小的相同子问题，分别解决后，再将子问题的解 合并 得到原问题的解。

  1. 分解
    将待排序序列按某种规则拆分成多个子序列，直到子问题规模足够小（通常为单个元素，天然有序）。
  2. 解决
    递归地对每个子序列进行排序。当子序列足够小（长度为 1 或 0）时，直接返回结果。
  3. 合并
    将已排序的子序列合并成更大的有序序列，最终得到完整的有序序列。

典型算法

  • 归并排序：从中间拆分，递归排序后合并，最典型的分治排序。
  • 快速排序：选定基准，通过分区将序列分为左右两部分，递归处理。

核心思想

实现过程

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];
  let i = 0,
    j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  while (i < left.length) result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);

  return result;
}

复杂度

时间复杂度

归并排序的时间复杂度稳定，不受数据初始顺序影响。

归并排序每次都将序列从中间一分为二，递归分解到单个元素，再两两合并：

  • 分解阶段：每次将序列对半划分，共需 log⁡2n\log_2 n 层
  • 合并阶段：每层合并都需要遍历所有 nn 个元素

最好情况：所有情况一致，复杂度均为 O(nlog⁡n)O(n \log n)

最坏情况：所有情况一致，复杂度均为 O(nlog⁡n)O(n \log n)

平均情况：所有情况一致，复杂度均为 O(nlog⁡n)O(n \log n)

详细推导：

第 1 层：nn 个元素，合并 n/2n/2 对，总比较次数为 nn
第 2 层：nn 个元素，合并 n/4n/4 对，总比较次数为 nn
……
第 log⁡2n\log_2 n 层：nn 个元素，合并 11 对，总比较次数为 nn

总比较次数：n×log⁡2n=O(nlog⁡n)n \times \log_2 n = O(n \log n)

情况 比较次数 时间复杂度
最好 nlog⁡2nn \log_2 n O(nlog⁡n)O(n \log n)
最坏 nlog⁡2nn \log_2 n O(nlog⁡n)O(n \log n)
平均 nlog⁡2nn \log_2 n O(nlog⁡n)O(n \log n)

空间复杂度

归并排序需要额外的存储空间来存放合并后的有序序列：

  • 递归版：每层递归需要 O(n)O(n) 的临时数组存储合并结果
  • 迭代版：同样需要 O(n)O(n) 的辅助数组
  • 总空间复杂度为 O(n)O(n)（递归栈空间为 O(log⁡n)O(\log n)，但辅助数组占主导）
版本 辅助数组 递归栈 总空间复杂度
递归版 O(n)O(n) O(log⁡n)O(\log n) O(n)O(n)
迭代版 O(n)O(n) O(1)O(1) O(n)O(n)

归并排序的 最大优势 是时间复杂度稳定，不受数据影响，且为 稳定排序。但需要额外的 O(n)O(n) 空间，这是其主要代价。

细节优化

算法特性

  1. 稳定性
    归并排序是 稳定排序，合并两个有序子序列时，当左右子序列的元素相等时，优先取左子序列的元素放入结果，确保相等元素的相对顺序不变。

    左子序列 [1, 2ₐ]，右子序列 [2ᵦ, 3]，合并时比较 2ₐ 和 2ᵦ，相等时取左子序列的 2ₐ，再取右子序列的 2ᵦ，最终序列为 [1, 2ₐ, 2ᵦ, 3]，相对顺序保持不变。

  2. 原地性
    归并排序属于 非原地排序，合并操作需要额外的辅助数组来存放合并后的有序序列，空间复杂度为 O(n)O(n)。虽然可通过原地归并技术将空间优化到 O(1)O(1)，但实现复杂且常数较大，实际应用中较少采用。

  3. 自适应性
    归并排序 不具备自适应性，无论数据是否有序，归并排序都严格按照 “分解 → 合并” 的流程执行，比较和合并的次数固定为 nlog⁡nn \log n，无法根据数据的有序程度提前优化。