经典排序算法：原理、优劣及应用 – wiki基地

---

经典排序算法：原理、优劣及应用深度解析

排序，是计算机科学中最基本且重要的问题之一。它指的是将一组数据按照特定的顺序（通常是升序或降序）重新排列。无论是在数据库查询优化、图形图像处理、操作系统内部管理，还是在日常的数据分析、文件整理中，排序都扮演着核心角色。掌握经典排序算法，不仅是理解数据结构与算法的基础，更是提升编程能力和解决实际问题的关键。

本文将深入探讨几种最经典、最具代表性的排序算法：冒泡排序、选择排序、插入排序、归并排序、快速排序和堆排序。我们将详细解析它们的原理、步骤、时间与空间复杂度分析，并讨论各自的优缺点及适用场景。

一、排序算法的基本概念与分类

在深入探讨具体算法之前，先明确几个基本概念：

• 稳定性 (Stability)：如果数组中有两个或多个相等元素，排序后这些相等元素的相对次序保持不变，则称该排序算法是稳定的。例如，如果元素 A 和 B 相等，且在原始数组中 A 在 B 之前，那么在稳定排序后的数组中，A 仍然在 B 之前。稳定性在处理带有附加信息的复杂数据对象时尤为重要。
• 原地排序 (In-place Sorting)：指算法在排序过程中，只需要少量额外的辅助空间来完成排序，通常这个额外空间的大小与待排序元素的个数无关（O(1) 空间复杂度），或者只与问题的递归深度有关（对于递归算法）。
• 时间复杂度 (Time Complexity)：衡量算法执行时间随着输入规模（通常是数据元素个数 n）增长而增长的速度。我们通常关注最好、平均和最坏情况下的时间复杂度，并使用大 O 记号表示。
• 空间复杂度 (Space Complexity)：衡量算法执行过程中所需的额外内存空间随着输入规模增长而增长的速度。

经典排序算法按其时间复杂度大致可分为两类：

1. 简单排序 (O(n^2))：包括冒泡排序、选择排序、插入排序。这类算法实现简单，但对于大规模数据效率较低。
2. 高级排序 (O(n log n))：包括归并排序、快速排序、堆排序。这类算法效率较高，是处理大规模数据的主流选择。

接下来，我们将逐一剖析这些经典算法。

二、简单排序算法 (O(n^2))

2.1 冒泡排序 (Bubble Sort)

• 原理：冒泡排序重复地遍历待排序的列表，一次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。遍历列表的工作是重复进行的，直到没有再需要交换，也就是说该列表已经排序完成。这个算法的名字由来是因为越小的元素会慢慢“浮”到列表的顶端。

• 步骤：

  1. 从列表的第一个元素开始，比较当前元素与下一个元素。
  2. 如果当前元素大于（升序排列）下一个元素，则交换它们的位置。
  3. 移动到下一个元素对，重复步骤 1 和 2，直到到达列表末尾。此时，最大的元素已经被“冒泡”到列表的最后一个位置。
  4. 对列表剩余部分（不包括最后一个已排序元素）重复步骤 1-3，直到整个列表排序完成。

• 示例：对数组 [5, 1, 4, 2, 8] 进行升序冒泡排序。

  • 第一趟：
    • (5, 1) -> (1, 5), [1, 5, 4, 2, 8]
    • (5, 4) -> (1, 4, 5, 2, 8)
    • (5, 2) -> (1, 4, 2, 5, 8)
    • (5, 8) -> (1, 4, 2, 5, 8] (8 已在最后位置)
  • 第二趟：
    • (1, 4) -> [1, 4, 2, 5, 8]
    • (4, 2) -> [1, 2, 4, 5, 8]
    • (4, 5) -> [1, 2, 4, 5, 8] (5 已在倒数第二个位置)
  • 第三趟：
    • (1, 2) -> [1, 2, 4, 5, 8]
    • (2, 4) -> [1, 2, 4, 5, 8] (4 已在倒数第三个位置)
  • 第四趟：
    • (1, 2) -> [1, 2, 4, 5, 8] (2 已在倒数第四个位置)
  • 排序完成：[1, 2, 4, 5, 8]

• 优化：可以在每一趟遍历后检查是否发生了交换。如果一整趟都没有发生交换，说明列表已经有序，可以直接停止排序。

• 伪代码：

  BubbleSort(arr):
n = length(arr)
for i from 0 to n-2: // 外层循环控制趟数，共 n-1 趟
swapped = false
for j from 0 to n-2-i: // 内层循环进行比较和交换
if arr[j] > arr[j+1]:
swap(arr[j], arr[j+1])
swapped = true
if not swapped: // 如果一趟没有交换，提前结束
break

• 复杂度分析：

  • 时间复杂度：无论最好、平均还是最坏情况，都需要进行大约 (n-1) + (n-2) + … + 1 = n(n-1)/2 次比较。最坏情况下每次比较都进行交换。
    • 最好情况 (已排序)：O(n)（通过优化，第一趟无交换即停止）
    • 平均情况：O(n^2)
    • 最坏情况 (逆序)：O(n^2)
  • 空间复杂度：O(1)（只需少量额外变量进行交换）
  • 稳定性：稳定（只有相邻元素相等时才不交换，保持相对次序）

• 优劣与应用：

  • 优点：概念简单，易于实现。
  • 缺点：效率极低，尤其对于大规模数据。
  • 应用：主要用于教学目的，或在数据量极小且对代码简洁性要求较高的情况下。

2.2 选择排序 (Selection Sort)

• 原理：选择排序将列表分为两个子序列：已排序子序列和未排序子序列。算法在未排序子序列中找到最小（或最大）元素，将其放到已排序子序列的末尾。这个过程重复进行，直到未排序子序列为空。

• 步骤：

  1. 从列表的第一个元素开始，将其视为已排序部分的末尾。
  2. 遍历未排序部分（从当前位置到列表末尾），找到最小元素的索引。
  3. 将最小元素与当前位置的元素进行交换。
  4. 将已排序部分的末尾向后移动一位，重复步骤 2-3，直到整个列表排序完成。

• 示例：对数组 [5, 1, 4, 2, 8] 进行升序选择排序。

  • 第一趟：
    • 未排序部分 [5, 1, 4, 2, 8]，最小元素是 1，位于索引 1。
    • 交换 arr[0] (5) 和 arr[1] (1)，数组变为 [1, 5, 4, 2, 8]。
    • 已排序部分 [1]，未排序部分 [5, 4, 2, 8]。
  • 第二趟：
    • 未排序部分 [5, 4, 2, 8]，最小元素是 2，位于索引 3 (相对于原始数组)。
    • 交换 arr[1] (5) 和 arr[3] (2)，数组变为 [1, 2, 4, 5, 8]。
    • 已排序部分 [1, 2]，未排序部分 [4, 5, 8]。
  • 第三趟：
    • 未排序部分 [4, 5, 8]，最小元素是 4，位于索引 2 (相对于原始数组)。
    • 交换 arr[2] (4) 和 arr[2] (4)，数组变为 [1, 2, 4, 5, 8]。
    • 已排序部分 [1, 2, 4]，未排序部分 [5, 8]。
  • 第四趟：
    • 未排序部分 [5, 8]，最小元素是 5，位于索引 3 (相对于原始数组)。
    • 交换 arr[3] (5) 和 arr[3] (5)，数组变为 [1, 2, 4, 5, 8]。
    • 已排序部分 [1, 2, 4, 5]，未排序部分 [8]。
  • 第五趟：
    • 未排序部分 [8]，只剩一个元素，已排序。
    • 排序完成：[1, 2, 4, 5, 8]

• 伪代码：

  SelectionSort(arr):
n = length(arr)
for i from 0 to n-2: // 外层循环控制已排序部分的边界
minIndex = i
for j from i+1 to n-1: // 内层循环在未排序部分找最小元素
if arr[j] < arr[minIndex]:
minIndex = j
if minIndex != i: // 如果最小元素不是当前位置的元素，则交换
swap(arr[i], arr[minIndex])

• 复杂度分析：

  • 时间复杂度：无论数据如何分布，外层循环执行 n-1 次，内层循环的比较次数依次是 n-1, n-2, …, 1。总比较次数约为 n(n-1)/2。交换次数最多为 n-1 次。
    • 最好、平均、最坏情况：O(n^2)
  • 空间复杂度：O(1)（只需少量额外变量）
  • 稳定性：不稳定（例如对 [5, 8, 5, 2] 进行选择排序，第一个 5 和 2 交换后，两个 5 的相对次序改变）

• 优劣与应用：

  • 优点：实现简单，交换次数固定且最少（n-1 次），这在某些场景下（如元素移动成本很高）可能是一个优点。
  • 缺点：效率低，时间复杂度固定为 O(n^2)。
  • 应用：主要用于教学，或在对交换次数有严格要求且数据量较小的情况下。

2.3 插入排序 (Insertion Sort)

• 原理：插入排序也把列表分为已排序和未排序两部分。它从列表的第二个元素开始，将每个元素视为一个待插入的元素，然后将该元素插入到已排序部分的正确位置上。这个过程就像我们在整理扑克牌，抓到一张新牌时，总是会将它插入到手中已有的牌的正确位置。

• 步骤：

  1. 将列表的第一个元素视为已排序部分。
  2. 从列表的第二个元素开始，依次取出每个元素，作为当前待插入元素 current。
  3. 在已排序部分（从后向前）查找 current 的插入位置。比较 current 与已排序部分的元素，如果已排序部分的元素大于 current，则将其向后移动一位。
  4. 重复步骤 3，直到找到一个不大于 current 的元素，或者到达已排序部分的起始位置。
  5. 将 current 插入到找到的位置。
  6. 重复步骤 2-5，直到所有元素都已插入。

• 示例：对数组 [5, 1, 4, 2, 8] 进行升序插入排序。

  • 已排序：[5]，未排序：[1, 4, 2, 8]。
  • 取出 1。已排序部分 [5]，5 > 1，5 后移。插入 1。数组变为 [1, 5, 4, 2, 8]。已排序：[1, 5]。
  • 取出 4。已排序部分 [1, 5]，5 > 4，5 后移。1 < 4，插入 4 在 1 后面。数组变为 [1, 4, 5, 2, 8]。已排序：[1, 4, 5]。
  • 取出 2。已排序部分 [1, 4, 5]，5 > 2，5 后移。4 > 2，4 后移。1 < 2，插入 2 在 1 后面。数组变为 [1, 2, 4, 5, 8]。已排序：[1, 2, 4, 5]。
  • 取出 8。已排序部分 [1, 2, 4, 5]，5 < 8，插入 8 在 5 后面。数组变为 [1, 2, 4, 5, 8]。已排序：[1, 2, 4, 5, 8]。
  • 排序完成：[1, 2, 4, 5, 8]。

• 伪代码：

  InsertionSort(arr):
n = length(arr)
for i from 1 to n-1: // 外层循环控制待插入元素
key = arr[i]
j = i - 1
// 内层循环在已排序部分查找插入位置并移动元素
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j = j - 1
arr[j+1] = key // 插入 key

• 复杂度分析：

  • 时间复杂度：取决于原始数据的有序程度。
    • 最好情况 (已排序)：O(n)（每个元素只需比较一次，不发生移动）
    • 平均情况：O(n^2)
    • 最坏情况 (逆序)：O(n^2)（每个元素都需要移动到已排序部分的起始位置）
  • 空间复杂度：O(1)（只需少量额外变量存储待插入元素）
  • 稳定性：稳定（当遇到与待插入元素相等的元素时，不会移动该相等元素，保持相对次序）

• 优劣与应用：

  • 优点：实现简单，原地排序，对于小规模数据或部分有序数据效率很高，是稳定的排序算法。
  • 缺点：对于大规模无序数据效率较低。
  • 应用：数组元素数量少时（例如小于几十个），作为混合排序算法（如 Timsort）的子算法使用，当输入数据已接近有序时。

三、高级排序算法 (O(n log n))

3.1 归并排序 (Merge Sort)

• 原理：归并排序是建立在归并操作上的一种有效、稳定的排序算法，采用分治（Divide and Conquer）策略。它将列表递归地分成较小的子列表，直到每个子列表只包含一个元素（单个元素自然是有序的），然后将这些有序的子列表两两合并（归并），最终得到一个完全有序的列表。

• 步骤：

  1. 分解 (Divide)：将待排序列表分成两半（直到列表只剩一个元素）。
  2. 解决 (Conquer)：递归地对两个子列表进行归并排序。
  3. 合并 (Combine)：将两个已排序的子列表合并成一个有序的列表。

• 合并 (Merge) 过程：

  • 创建一个新的临时列表，其大小等于两个子列表的总和。
  • 使用两个指针，分别指向两个已排序子列表的起始位置。
  • 比较两个指针指向的元素，将较小的那个添加到临时列表，并移动相应子列表的指针。
  • 重复比较和添加，直到其中一个子列表的所有元素都被添加到临时列表。
  • 将另一个子列表中剩余的元素全部添加到临时列表的末尾。
  • 将临时列表的元素复制回原列表对应的位置。

• 示例：对数组 [5, 1, 4, 2, 8, 3, 7, 6] 进行升序归并排序。

  • 分解：[5, 1, 4, 2] 和 [8, 3, 7, 6]
  • 分解：[5, 1], [4, 2] 和 [8, 3], [7, 6]
  • 分解：[5], [1], [4], [2] 和 [8], [3], [7], [6] (到达基本情况)
  • 合并：[1, 5], [2, 4] 和 [3, 8], [6, 7]
  • 合并：[1, 2, 4, 5] 和 [3, 6, 7, 8]
  • 合并：[1, 2, 3, 4, 5, 6, 7, 8]
  • 排序完成：[1, 2, 3, 4, 5, 6, 7, 8]

• 伪代码：

  “`
  MergeSort(arr, left, right):
  if left < right:
  mid = (left + right) / 2
  MergeSort(arr, left, mid) // 递归左半部分
  MergeSort(arr, mid+1, right) // 递归右半部分
  Merge(arr, left, mid, right) // 合并两个有序部分

  Merge(arr, left, mid, right):
  // 创建临时数组 L 和 R
  n1 = mid – left + 1
  n2 = right – mid
  L = new array of size n1
  R = new array of size n2

  // 复制数据到临时数组 L 和 R
  for i from 0 to n1-1: L[i] = arr[left + i]
  for j from 0 to n2-1: R[j] = arr[mid + 1 + j]
  
  // 合并临时数组到原数组 arr[left..right]
  i = 0 // L 的初始索引
  j = 0 // R 的初始索引
  k = left // 合并到 arr 的初始索引
  
  while i < n1 and j < n2:
      if L[i] <= R[j]:
          arr[k] = L[i]
          i = i + 1
      else:
          arr[k] = R[j]
          j = j + 1
      k = k + 1
  
  // 复制剩余元素
  while i < n1:
      arr[k] = L[i]
      i = i + 1
      k = k + 1
  
  while j < n2:
      arr[k] = R[j]
      j = j + 1
      k = k + 1
  

  “`

• 复杂度分析：

  • 时间复杂度：无论输入数据如何，分解过程产生 log n 层递归，每一层合并操作的时间复杂度为 O(n)。
    • 最好、平均、最坏情况：O(n log n)
  • 空间复杂度：O(n)（需要额外的临时空间进行合并操作）
  • 稳定性：稳定（合并过程中，如果两个元素相等，先放左边子列表的元素，可以保持相对次序）

• 优劣与应用：

  • 优点：时间复杂度稳定且效率较高 (O(n log n))，是稳定的排序算法，适用于链表结构（无需物理移动元素，只需修改指针）。
  • 缺点：需要额外的 O(n) 空间，这在内存受限的环境下可能是一个问题；递归实现有额外的函数调用开销。
  • 应用：对稳定性有要求，且对内存空间不是特别敏感的场景；外部排序（数据量过大无法一次加载到内存）。

3.2 快速排序 (Quick Sort)

• 原理：快速排序是实践中效率最高的排序算法之一，也采用分治策略。它选择一个元素作为“基准”（pivot），通过一趟扫描将待排序列表分割成独立的两部分：一部分所有元素都比基准小，另一部分所有元素都比基准大。然后递归地对这两部分进行快速排序。

• 步骤：

  1. 选择基准 (Pick Pivot)：从列表中选择一个元素作为基准。选择基准的方法有很多种，如选择第一个、最后一个、中间元素，或随机选择。
  2. 分区 (Partition)：重新排列列表，将所有小于基准的元素放在基准前面，所有大于基准的元素放在基准后面。等于基准的元素可以放在任意一边。分区结束后，基准就位于其最终的排序位置上。
  3. 递归 (Recurse)：递归地对基准前后的两个子列表进行快速排序。

• 分区 (Partition) 过程：一种常用的分区方法是双指针法。

  • 选择一个基准元素 (例如，最后一个元素)。
  • 维护一个指针 i，指向小于基准元素的区域的末尾。
  • 遍历列表 (指针 j 从开始位置到基准前一个位置)。如果 arr[j] 小于等于基准，则将 arr[j] 与 arr[i+1] 交换，并递增 i。
  • 遍历结束后，将基准元素 (原 arr[right]) 与 arr[i+1] 交换。此时，arr[i+1] 就是基准的最终位置。

• 示例：对数组 [5, 1, 4, 2, 8] 进行升序快速排序 (选择最后一个元素 8 作为初始基准)。

  • 初始：[5, 1, 4, 2, 8]。基准 = 8。
  • 分区：[5, 1, 4, 2 | 8]。遍历 [5, 1, 4, 2]。
    • 5 <= 8，i=0。
    • 1 <= 8，交换 arr[1] 和 arr[0+1] (1和1)，i=1。
    • 4 <= 8，交换 arr[2] 和 arr[1+1] (4和4)，i=2。
    • 2 <= 8，交换 arr[3] 和 arr[2+1] (2和2)，i=3。
  • 遍历结束，交换基准 8 和 arr[3+1] (arr[4])。数组仍是 [5, 1, 4, 2, 8]。基准 8 在位置 4。
  • 递归对 [5, 1, 4, 2] 进行快速排序。选择 2 作为基准。
    • [5, 1, 4 | 2]。遍历 [5, 1, 4]。i = -1。
    • 5 > 2。
    • 1 <= 2，交换 arr[1] 和 arr[0] (1和5)。数组变为 [1, 5, 4 | 2]。i=0。
    • 4 > 2。
  • 遍历结束，交换基准 2 和 arr[0+1] (arr[1])。数组变为 [1, 2, 4, 5]。基准 2 在位置 1。
  • 递归对 [1] (已排序) 和 [4, 5] 进行快速排序。
    • 对 [4, 5]，选择 5 为基准。
    • 分区：[4 | 5]。4 <= 5，i=0。交换 5 和 arr[1]。仍是 [4, 5]。基准 5 在位置 1。
    • 递归对 [4] (已排序)。
  • 所有子列表都已排序并归位，最终得到 [1, 2, 4, 5, 8]。

• 伪代码：

  “`
  QuickSort(arr, low, high):
  if low < high:
  // pi 是分区索引，arr[pi] 现在在其正确位置
  pi = Partition(arr, low, high)
  QuickSort(arr, low, pi – 1) // 递归排序前一部分
  QuickSort(arr, pi + 1, high) // 递归排序后一部分

  Partition(arr, low, high):
  pivot = arr[high] // 选择最后一个元素作为基准
  i = low – 1 // 小于基准元素的索引

  for j from low to high - 1:
      // 如果当前元素小于或等于基准
      if arr[j] <= pivot:
          i = i + 1
          swap(arr[i], arr[j])
  
  swap(arr[i + 1], arr[high]) // 将基准放到正确位置
  return i + 1 // 返回基准的最终索引
  

  “`

• 复杂度分析：

  • 时间复杂度：取决于基准的选择。
    • 最好情况 (每次都均匀分成两半)：O(n log n)
    • 平均情况：O(n log n)
    • 最坏情况 (每次都选择最大或最小元素作为基准，导致一边是 n-1 个元素，另一边是 0 个)：O(n^2)
  • 空间复杂度：取决于递归调用的深度。
    • 平均情况：O(log n)（递归栈空间）
    • 最坏情况：O(n)（当出现最坏时间复杂度时）
  • 稳定性：不稳定（分区过程中，可能会交换相等的元素，改变它们的相对次序）

• 优劣与应用：

  • 优点：在平均情况下性能优异，是实践中最快的排序算法之一；原地排序 (O(1) 额外空间用于分区，O(log n) 平均递归栈空间)；良好的缓存局部性。
  • 缺点：最坏情况时间复杂度为 O(n^2)，且空间复杂度退化为 O(n)；不稳定；性能高度依赖于基准选择策略。
  • 应用：大多数编程语言的标准库排序实现都使用了快速排序（通常是经过优化的，如采用三数取中法选择基准，或结合插入排序处理小规模子问题，甚至使用 Introsort 避免最坏情况）。适用于大规模数据的通用排序。

3.3 堆排序 (Heap Sort)

• 原理：堆排序是利用堆（Heap）这种数据结构所设计的一种排序算法。堆是一种近似完全二叉树的结构，并满足堆的性质：即子结点的键值或索引总是小于（或大于）它的父结点。根据堆性质的不同，堆可分为最大堆（父节点大于子节点）和最小堆（父节点小于子节点）。堆排序利用最大堆来实现升序排序，或利用最小堆实现降序排序。

• 步骤 (以最大堆实现升序为例)：

  1. 构建最大堆 (Build Max Heap)：将待排序列表构建成一个最大堆。最大元素位于堆的根节点。
  2. 排序 (Sort)：重复执行以下操作直到堆为空：
     • 将堆顶元素（最大元素）与堆的最后一个元素交换。
     • 将堆的大小减一（此时原最大元素已在正确的位置，不再参与堆操作）。
     • 对新的堆顶元素进行堆化 (Heapify)，使其满足最大堆性质（将堆顶元素向下调整，使其在其子树中找到正确位置）。

• 构建最大堆过程：从最后一个非叶子节点开始，对其进行堆化，然后向前依次对其父节点进行堆化，直到根节点。

• 堆化 (Heapify) 过程 (向下调整)：对于给定的节点 i：

  • 比较节点 i 与其左子节点 (2i+1) 和右子节点 (2i+2) 的值。
  • 找出它们中值最大的那个节点（或自身）。
  • 如果最大值不是节点 i 本身，则将节点 i 与最大值的那个节点交换。
  • 交换后，可能破坏了被交换子节点的堆性质，因此需要递归地对被交换的子节点重复堆化过程，直到节点 i 的子树满足最大堆性质。

• 示例：对数组 [4, 10, 3, 5, 1, 2] 进行升序堆排序。

  • 初始数组：[4, 10, 3, 5, 1, 2]
  • 构建最大堆：从最后一个非叶子节点 (索引 2，值 3) 开始堆化。
    • 对索引 2 (3)：其子节点 5, 1。最大是 5。3 < 5，交换 3 和 5。数组变为 [4, 10, 5, 3, 1, 2]。
    • 对索引 1 (10)：其子节点 3, 1。最大是 10。10 >= 3, 1。无需交换。
    • 对索引 0 (4)：其子节点 10, 5。最大是 10。4 < 10，交换 4 和 10。数组变为 [10, 4, 5, 3, 1, 2]。交换后索引 1 (4) 的子树可能不满足堆性质，需要对索引 1 进行堆化。对索引 1 (4) 堆化：其子节点 3, 1。最大是 4。无需交换。
  • 最大堆构建完成：[10, 4, 5, 3, 1, 2] (视觉上看不是标准二叉树形状，但满足父>子性质)
  • 排序：
    • 交换堆顶 (10) 和最后一个元素 (2)：[2, 4, 5, 3, 1, 10]。堆大小为 5。
    • 对堆顶 (2) 堆化：子节点 4, 5。最大 5。交换 2 和 5：[5, 4, 2, 3, 1, 10]。对索引 2 (2) 堆化：子节点 1。最大 2。无需交换。当前堆：[5, 4, 2, 3, 1]。
    • 交换堆顶 (5) 和最后一个元素 (1)：[1, 4, 2, 3, 5, 10]。堆大小为 4。
    • 对堆顶 (1) 堆化：子节点 4, 2。最大 4。交换 1 和 4：[4, 1, 2, 3, 5, 10]。对索引 1 (1) 堆化：子节点 3。最大 3。交换 1 和 3：[4, 3, 2, 1, 5, 10]。对索引 3 (1) 堆化：无子节点。当前堆：[4, 3, 2, 1]。
    • 交换堆顶 (4) 和最后一个元素 (1)：[1, 3, 2, 4, 5, 10]。堆大小为 3。
    • 对堆顶 (1) 堆化：子节点 3, 2。最大 3。交换 1 和 3：[3, 1, 2, 4, 5, 10]。对索引 1 (1) 堆化：子节点 2。最大 2。交换 1 和 2：[3, 2, 1, 4, 5, 10]。对索引 2 (1) 堆化：无子节点。当前堆：[3, 2, 1]。
    • 交换堆顶 (3) 和最后一个元素 (1)：[1, 2, 3, 4, 5, 10]。堆大小为 2。
    • 对堆顶 (1) 堆化：子节点 2。最大 2。交换 1 和 2：[2, 1, 3, 4, 5, 10]。对索引 1 (1) 堆化：无子节点。当前堆：[2, 1]。
    • 交换堆顶 (2) 和最后一个元素 (1)：[1, 2, 3, 4, 5, 10]。堆大小为 1。
    • 堆大小为 1，排序完成。最终数组：[1, 2, 3, 4, 5, 10]。

• 伪代码：

  “`
  HeapSort(arr):
  n = length(arr)

  // 1. 构建最大堆
  // 从最后一个非叶子节点开始 (n/2 - 1) 向前堆化
  for i from n / 2 - 1 down to 0:
      Heapify(arr, n, i)
  
  // 2. 逐个提取元素进行排序
  for i from n - 1 down to 0:
      // 将当前根节点(最大元素)与末尾元素交换
      swap(arr[0], arr[i])
      // 对剩余的堆进行堆化，新的堆大小为 i
      Heapify(arr, i, 0)
  

  // 堆化函数：维持最大堆性质
  // arr[] 是数组，n 是堆的大小，i 是当前需要调整的根节点索引
  Heapify(arr, n, i):
  largest = i // 初始化最大元素索引为根节点
  left = 2 * i + 1 // 左子节点索引
  right = 2 * i + 2 // 右子节点索引

  // 如果左子节点比根节点大
  if left < n and arr[left] > arr[largest]:
      largest = left
  
  // 如果右子节点比当前最大元素(可能是左子节点)大
  if right < n and arr[right] > arr[largest]:
      largest = right
  
  // 如果最大元素不是根节点
  if largest != i:
      swap(arr[i], arr[largest])
      // 对交换后的子树进行递归堆化
      Heapify(arr, n, largest)
  

  “`

• 复杂度分析：

  • 时间复杂度：构建最大堆的过程时间复杂度为 O(n)。排序过程需要进行 n-1 次堆化操作，每次堆化的时间复杂度为 O(log n) (因为堆的高度是 log n)。因此总时间复杂度为 O(n + n log n) = O(n log n)。
    • 最好、平均、最坏情况：O(n log n)
  • 空间复杂度：O(1)（所有操作都在原地进行，只需少量额外变量用于交换和索引）
  • 稳定性：不稳定（堆化过程中，父节点和子节点交换可能会改变相等元素的相对次序）

• 优劣与应用：

  • 优点：时间复杂度稳定为 O(n log n)，是原地排序算法 (O(1) 额外空间)，适用于对空间要求严格的场景。
  • 缺点：不稳定；相较于快速排序，堆排序的常量因子较大，实际运行速度通常略慢；对于缓存不友好（访问的元素分散）。
  • 应用：在内存受限且需要 O(n log n) 最坏时间复杂度保证的场景；实现优先队列 (Priority Queue) 的基础数据结构。

四、经典排序算法对比总结

算法	时间复杂度 (最好/平均/最坏)	空间复杂度	稳定性	原地排序	实现难度
冒泡排序	O(n)/O(n^2)/O(n^2)	O(1)	稳定	是	简单
选择排序	O(n^2)/O(n^2)/O(n^2)	O(1)	不稳定	是	简单
插入排序	O(n)/O(n^2)/O(n^2)	O(1)	稳定	是	简单
归并排序	O(n log n)/O(n log n)/O(n log n)	O(n)	稳定	否	中等
快速排序	O(n log n)/O(n log n)/O(n^2)	O(log n) 或 O(n)	不稳定	是 (分区 O(1))	中等
堆排序	O(n log n)/O(n log n)/O(n log n)	O(1)	不稳定	是	中等

五、如何选择合适的排序算法？

选择哪种排序算法取决于多种因素：

1. 数据规模：

   • 数据量小 (几十到几百)：O(n^2) 算法（如插入排序）可能因为实现简单、常数因子小而比 O(n log n) 算法更快。
   • 数据量大：优先选择 O(n log n) 算法（快速排序、归并排序、堆排序）。

2. 数据的有序程度：

   • 数据接近有序：插入排序的性能接近 O(n)，非常高效。
   • 数据完全无序或逆序：O(n log n) 算法更合适。

3. 内存限制：

   • 内存非常有限：选择原地排序算法（冒泡、选择、插入、快速、堆排序）。堆排序和快速排序在 O(1) 或 O(log n) 空间下是较好的选择。
   • 内存充足：归并排序也是不错的选择，尤其对稳定性有要求时。

4. 稳定性要求：

   • 如果需要保持相等元素的相对次序：选择稳定排序算法（冒泡、插入、归并）。

5. 最坏情况性能要求：

   • 需要保证最坏情况下的性能：选择归并排序或堆排序 (O(n log n))。快速排序的最坏情况是 O(n^2)，虽然在实践中很少出现，但在需要严格性能保证的场景下应谨慎使用或采用优化策略。

6. 实现难度：

   • 教学或快速原型：简单排序算法（冒泡、选择、插入）。
   • 实际应用：通常使用库函数，它们往往是经过高度优化的混合算法（如 Java 的 Arrays.sort() 对原始类型使用双轴快速排序，对对象使用 Timsort；Python 的 list.sort() 使用 Timsort；C++ 的 std::sort() 通常使用 Introsort）。

六、超越经典：混合排序与特定场景排序

现代编程语言的标准库通常不会直接使用一个简单的经典算法，而是使用混合排序算法。例如：

• Timsort：Python、Java、Android 等使用的一种混合排序算法，它结合了归并排序和插入排序。它利用了现实世界中许多数据包含已排序子序列（称为 run）的特点，对 run 使用插入排序进行扩展或创建，然后使用归并排序合并这些 run。对接近有序的数据表现极佳，且是稳定的。
• Introsort (内省排序)：C++ STL 的 std::sort 常用的实现。它是快速排序的变体，当递归深度超过某个阈值时，会切换到堆排序，以避免快速排序在最坏情况下的 O(n^2) 性能。
• 双轴快速排序 (Dual-Pivot Quick Sort)：Java 7 引入的快速排序变体，选择两个基准，将数组分为三部分。在实践中比标准快速排序更快。

此外，还有一些不依赖比较的线性时间复杂度排序算法 (O(n))，适用于特定类型的数据：

• 计数排序 (Counting Sort)：适用于待排序元素是整数，且范围不大的情况。
• 桶排序 (Bucket Sort)：适用于待排序元素均匀分布在一个范围内的情况。
• 基数排序 (Radix Sort)：适用于待排序元素可以按位或按字符串进行比较的情况。

这些算法虽然高效，但对数据类型或分布有特定要求，不如比较排序算法普适。

七、结论

经典排序算法是计算机科学算法设计基石，它们不仅是解决排序问题的工具，更是理解分治、递归、数据结构（如堆）、算法分析（时间/空间复杂度）等核心概念的绝佳范例。

冒泡、选择、插入排序简单直观，适合初学者理解排序的基本思想，但效率低下。归并排序稳定且性能可靠，但需要额外空间。快速排序在平均情况下表现最佳，是实践中常用的选择，但存在最坏情况。堆排序提供了稳定的 O(n log n) 性能和 O(1) 空间，是空间受限场景下的有力竞争者。

在实际开发中，我们通常依赖于语言标准库提供的优化过的排序函数。然而，深入理解这些经典算法的原理、优劣和应用，对于分析算法性能、解决特定问题、甚至设计更优化的算法，都具有不可估量的价值。它们是算法学习的必经之路，也是通往更高级算法和数据结构世界的敲门砖。

---