我已为您将上述关于**“基于比较的排序算法”**的讲义内容进行了整理与深度优化。

在本次整理中，我完成了以下工作：
1. **消除了复制杂质**：去除了所有代码块末尾残留的网页行号，并规范了原本由于复制导致的断行。
2. **规范化数学公式**：使用标准 LaTeX 语法渲染了所有数组、算法复杂度（如 $O(n \log n)$、$O(n^2)$ 等）、以及排序比较与交换次数的推导公式。
3. **修复了代码中的逻辑错误**：
   * 在“堆排序”的 `main` 函数中，原内容包含了一行多余且错误的 `srt(a, 0, n - 1);` 调用注释。我已将其精简移除，使 C++ 代码可直接编译运行。
4. **统一了小结表格**：对最后一块的复杂度大表进行了排版对齐，使各算法的各项指标更加直观。

以下是整理后的完整 Markdown 内容：

---

# 基于比较的排序算法

在计算机科学中，**排序（Sorting）**是最基础且最重要的一类问题。简单来说，排序就是将一组杂乱无章的数据元素，按照某种预定的规则（例如，数值从小到大、字典序等）重新排列成一个有序序列的过程。

例如，给定一个整数数组 $A = \{5, 2, 8, 1, 9\}$，我们希望将其按照从小到大的顺序排序，得到的结果将是 $B = \{1, 2, 5, 8, 9\}$。这个从数组 $A$ 到数组 $B$ 的过程，就是一个排序过程。

---

## 一、 排序算法的性能衡量指标

排序算法的优劣通常由其运行效率来衡量，主要体现在以下三个方面：

1. **时间复杂度（Time Complexity）**：算法执行所需的时间，通常通过**比较次数**和**交换次数**（或移动次数）来衡量。
2. **空间复杂度（Space Complexity）**：算法执行过程中额外占用的内存空间。
3. **稳定性（Stability）**：指在待排序的序列中，若存在多个具有相同关键字的元素，经过排序后，这些元素的原有相对顺序保持不变。
   * **定义**：设序列中存在两个元素 $a$ 和 $b$，它们的关键字相同（即 $key(a) = key(b)$），且在排序前 $a$ 在 $b$ 前面。若排序后 $a$ 仍然在 $b$ 的前面，则该排序算法是**稳定**的；反之，若相对位置可能发生改变，则称该算法是**不稳定**的。

### 排序算法的两大门派
* **比较类排序**：通过比较元素之间的关键字大小来决定元素的相对次序。其时间复杂度的理论下限是 $O(n \log n)$。常见的比较类排序有冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序和堆排序。
* **非比较类排序**：不通过比较来确定元素顺序，而是利用元素自身的特性（如数值范围、位数等）来进行排序，可以突破 $O(n \log n)$ 的下限达到线性时间 $O(n)$。常见的有计数排序、基数排序和桶排序。

*本节重点介绍基于比较的排序算法。*

---

## 二、 七大基于比较的排序算法详解

### 1. 冒泡排序 (Bubble Sort)

#### 1.1 核心思想
通过重复地遍历待排序序列，依次比较相邻的两个元素。如果它们的顺序错误（如前一个比后一个大），就交换它们。

这个过程会一直重复，直到在某一次遍历中**没有发生任何元素交换**，这意味着整个序列已经变得有序。在从小到大排序的过程中，较小的元素会经过交换慢慢地“浮”到序列的顶部，而较大的元素则会“沉”到序列的底部。

#### 1.2 分步图解
假设待排序数组为 $A = \{6, 5, 3, 1, 8, 7, 2, 4\}$。

* **第一趟**：目标是将当前序列的最大值 $8$ 移动到最后。
  1. 比较 $A[0]$ 和 $A[1]$（$6$ 和 $5$）。$6 > 5$，交换。序列变为 $\{5, 6, 3, 1, 8, 7, 2, 4\}$。
  2. 比较 $A[1]$ 和 $A[2]$（$6$ 和 $3$）。$6 > 3$，交换。序列变为 $\{5, 3, 6, 1, 8, 7, 2, 4\}$。
  3. 比较 $A[2]$ 和 $A[3]$（$6$ 和 $1$）。$6 > 1$，交换。序列变为 $\{5, 3, 1, 6, 8, 7, 2, 4\}$。
  4. 比较 $A[3]$ 和 $A[4]$（$6$ 和 $8$）。$6 < 8$，不交换。序列不变。
  5. 比较 $A[4]$ 和 $A[5]$（$8$ 和 $7$）。$8 > 7$，交换。序列变为 $\{5, 3, 1, 6, 7, 8, 2, 4\}$。
  6. 比较 $A[5]$ 和 $A[6]$（$8$ 和 $2$）。$8 > 2$，交换。序列变为 $\{5, 3, 1, 6, 7, 2, 8, 4\}$。
  7. 比较 $A[6]$ 和 $A[7]$（$8$ 和 $4$）。$8 > 4$，交换。序列变为 $\{5, 3, 1, 6, 7, 2, 4, 8\}$。
  * **结果**：第一趟结束，最大元素 $8$ 已经“沉”到了数组末尾。
* **第二趟**：目标是将剩余 $n-1$ 个元素中的最大值 $7$ 移动到倒数第二位，比较范围缩减为 $A[0]$ 到 $A[6]$。
  1. 比较 $5$ 和 $3$ $\to$ 交换 $\to$ $\{3, 5, 1, 6, 7, 2, 4, 8\}$
  2. 比较 $5$ 和 $1$ $\to$ 交换 $\to$ $\{3, 1, 5, 6, 7, 2, 4, 8\}$
  3. 比较 $5$ 和 $6$ $\to$ 不交换
  4. 比较 $6$ 和 $7$ $\to$ 不交换
  5. 比较 $7$ 和 $2$ $\to$ 交换 $\to$ $\{3, 1, 5, 6, 2, 7, 4, 8\}$
  6. 比较 $7$ 和 $4$ $\to$ 交换 $\to$ $\{3, 1, 5, 6, 2, 4, 7, 8\}$
  * **结果**：次大元素 $7$ 就位。

#### 1.3 优化思路
如果在某一趟遍历中，没有发生任何一次交换，说明整个序列已经完全有序，可提前结束排序。例如对有序数组进行检验，或提前排好序时直接跳出。

#### 1.4 C++ 代码实现

##### 基础版本
```cpp
#include <iostream>
#include <algorithm>
using namespace std;

void bub(int a[], int n) {
    // 外层循环控制趟数
    for (int i = 0; i < n - 1; ++i) {
        // 内层循环负责每趟的相邻元素比较
        // 因为末尾 i 个元素已有序，故上界为 n - 1 - i
        for (int j = 0; j < n - 1 - i; ++j) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
            }
        }
    }
}

int main() {
    int a[] = {6, 5, 3, 1, 8, 7, 2, 4};
    int n = sizeof(a) / sizeof(a[0]);
    bub(a, n);
    for (int i = 0; i < n; ++i) cout << a[i] << " ";
    cout << endl;
    return 0;
}
```

##### 优化版本（加入交换标志位）
```cpp
#include <iostream>
#include <algorithm>
using namespace std;

void bub_optimized(int a[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        bool flg = false; // 默认为 false 表示未发生交换
        for (int j = 0; j < n - 1 - i; ++j) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                flg = true; // 发生了交换
            }
        }
        // 若此趟遍历无任何交换，说明已有序，直接提前退出
        if (!flg) break;
    }
}

int main() {
    int a[] = {1, 2, 3, 5, 4};
    int n = sizeof(a) / sizeof(a[0]);
    bub_optimized(a, n);
    for (int i = 0; i < n; ++i) cout << a[i] << " ";
    cout << endl;
    return 0;
}
```

#### 1.5 复杂度与性质详解
* **比较次数**：
  无论初始状态如何，基础版本的总比较次数 $C(n)$ 为恒定值：
  $$C(n) = (n-1) + (n-2) + \dots + 1 = \sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = O(n^2)$$
  优化版本在最好情况（已排序）下只需比较 $n-1$ 次，即 $O(n)$。
* **交换次数**：
  * **最坏情况（完全逆序）**：
    $$S_{max}(n) = \frac{n(n-1)}{2} = O(n^2)$$
  * **最好情况（已有序）**：$0$ 次。
  * **平均情况**：随机序列的平均交换次数约为 $\frac{n(n-1)}{4}$，仍属于 $O(n^2)$。
* **稳定性**：**稳定**。只有在满足 $a[j] > a[j+1]$ 的严格不等式时才发生交换，元素相等时不交换，因此相等元素的相对顺序不会发生改变。
* **空间复杂度**：$O(1)$，原地排序。

---

### 2. 选择排序 (Selection Sort)

#### 2.1 核心思想
每一轮在未排序的序列中找到最小（或最大）的元素，然后将其放置到已排序序列的末尾。

#### 2.2 算法步骤
1. 在未排序序列 $A[0 \dots n-1]$ 中找到最小元素，与 $A[0]$ 交换。
2. 在未排序序列 $A[1 \dots n-1]$ 中找到最小元素，与 $A[1]$ 交换。
3. 重复此过程，直到剩下最后一个元素，排序完毕。

#### 2.3 复杂度与性质
* **时间复杂度**：始终为 $O(n^2)$。比较次数与初始排列无关，必须完整执行两重循环。
* **空间复杂度**：$O(1)$，原地排序。
* **稳定性**：**不稳定**。例如序列 $\{5_a, 8, 5_b, 2, 9\}$，第一轮找到最小值 $2$，与首位 $5_a$ 交换后变为 $\{2, 8, 5_b, 5_a, 9\}$，两个 $5$ 的相对顺序发生了改变。

#### 2.4 C++ 代码实现
```cpp
#include <iostream>
#include <algorithm>
using namespace std;

void sel(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i; // 记录当前轮次最小元素的索引
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            swap(a[i], a[min_idx]);
        }
    }
}

int main() {
    int a[] = {5, 2, 8, 1, 9, 4};
    int n = sizeof(a) / sizeof(a[0]);
    sel(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
```

---

### 3. 插入排序 (Insertion Sort)

#### 3.1 核心思想
将待排序序列分为“已排序”和“未排序”两部分。每次从未排序部分取出一个元素，插入到已排序部分的正确位置。

#### 3.2 算法步骤
1. 将第一个元素视为初始的已排序序列。
2. 从第二个元素开始，作为待插入元素 `cur`。
3. 将 `cur` 与已排序序列中的元素从后向前依次比较。
4. 若已排序元素大于 `cur`，则将该元素向后移动一位。
5. 重复移动，直至找到小于或等于 `cur` 的位置，将 `cur` 插入。

#### 3.3 复杂度与性质
* **时间复杂度**：
  * **最好情况**：$O(n)$，当序列已经有序时，内层循环只比较一次就停止，无需移动。
  * **最坏情况**：$O(n^2)$，序列完全逆序。
  * **平均情况**：$O(n^2)$。
* **空间复杂度**：$O(1)$，原地排序。
* **稳定性**：**稳定**。移动元素时只有在严格大于 `cur` 时才向后移，若相等则停止移动，故不会打乱相对位置。

#### 3.4 C++ 代码实现
```cpp
#include <iostream>
using namespace std;

void ins(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int cur = a[i]; // 待插入元素
        int j = i - 1;
        // 在已排序部分 a[0...i-1] 中寻找插入位置
        while (j >= 0 && a[j] > cur) {
            a[j + 1] = a[j]; // 元素后移
            j--;
        }
        a[j + 1] = cur; // 插入
    }
}

int main() {
    int a[] = {5, 2, 8, 1, 9, 4};
    int n = sizeof(a) / sizeof(a[0]);
    ins(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
```

---

### 4. 希尔排序 (Shell Sort)

#### 4.1 核心思想
希尔排序是插入排序的一种高效改进版本。它通过将整个序列按某个“增量” `gap` 分成若干个子序列，对每个子序列分别进行直接插入排序。随着增量逐渐减小直至 `gap = 1`，序列已基本有序，最后再进行一次常规插入排序，效率将非常高。

#### 4.2 算法步骤
1. 选择一个增量序列（常用初始增量为 $gap = n/2$，每次减半）。
2. 根据当前的 `gap`，将序列分为 `gap` 个子序列，子序列内的元素物理间距为 `gap`。
3. 对这些子序列分别进行直接插入排序。
4. 减小增量 `gap`，重复上述步骤。
5. 直到 $gap = 1$，对全体元素进行最后一次插入排序。

#### 4.3 复杂度与性质
* **时间复杂度**：依赖于增量序列的选择。
  * 平均情况下一般在 $O(n \log n)$ 到 $O(n^{1.5})$ 之间。
  * 最坏情况若使用除 2 减半的序列，仍为 $O(n^2)$。
* **空间复杂度**：$O(1)$。
* **稳定性**：**不稳定**。在分组子序列交叉进行排序时，相同关键字的元素可能被划分到不同子序列中，发生跨越式交换，导致相对顺序被打乱。

#### 4.4 C++ 代码实现
```cpp
#include <iostream>
using namespace std;

void shl(int a[], int n) {
    // 增量 gap 从 n/2 开始，每次减半
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个子序列进行插入排序
        for (int i = gap; i < n; i++) {
            int cur = a[i];
            int j = i - gap;
            while (j >= 0 && a[j] > cur) {
                a[j + gap] = a[j];
                j -= gap;
            }
            a[j + gap] = cur;
        }
    }
}

int main() {
    int a[] = {5, 2, 8, 1, 9, 4, 3, 7, 6};
    int n = sizeof(a) / sizeof(a[0]);
    shl(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
```

---

### 5. 归并排序 (Merge Sort)

#### 5.1 核心思想
归并排序是分治法（Divide and Conquer）的典型应用。其基本思路是“先递归分解，再双指针合并结果”。

#### 5.2 算法步骤
1. **分解（Divide）**：将当前序列从中间对半切分，递归执行，直至子序列长度为 $1$。
2. **合并（Combine）**：将相邻的两个有序子序列合并成一个更大的有序序列。使用双指针分别指向两个子序列头部，挑选较小的元素放入临时数组，最后将临时数组写回原数组。

#### 5.3 复杂度与性质
* **时间复杂度**：始终为 $O(n \log n)$。分解层数为 $\log_2 n$ 层，每层合并的开销是线性的 $O(n)$。性能极为稳定，不受初始数据形态影响。
* **空间复杂度**：$O(n)$，合并过程中需要开辟与待合并元素总数等长的辅助空间。
* **稳定性**：**稳定**。在合并过程中，若遇两个元素相等，我们规定优先把第一个子序列中的元素拷入临时数组，即可完美保证稳定性。

#### 5.4 C++ 代码实现
```cpp
#include <iostream>
#include <vector>
using namespace std;

// 合并两个有序区间 a[l...m] 和 a[m+1...r]
void mrg(int a[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    vector<int> L(n1), R(n2);

for (int i = 0; i < n1; i++) L[i] = a[l + i];
    for (int j = 0; j < n2; j++) R[j] = a[m + 1 + j];

int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            a[k++] = L[i++];
        } else {
            a[k++] = R[j++];
        }
    }
    while (i < n1) a[k++] = L[i++];
    while (j < n2) a[k++] = R[j++];
}

void srt_merge(int a[], int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2; // 二分
    srt_merge(a, l, m);
    srt_merge(a, m + 1, r);
    mrg(a, l, m, r);         // 合并
}

int main() {
    int a[] = {5, 2, 8, 1, 9, 4};
    int n = sizeof(a) / sizeof(a[0]);
    srt_merge(a, 0, n - 1);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
```

---

### 6. 快速排序 (Quick Sort)

#### 6.1 核心思想
同样基于分治法。它通过一趟划分将待排记录分隔成独立的两部分，使得其中一部分的所有数据都比另一部分小。然后，递归地对这两部分数据继续进行快速排序。

#### 6.2 算法步骤
1. **选择基准（Pivot）**：从序列中选出一个元素作为基准。
2. **分区（Partition）**：通过交换，将所有比基准小的元素移到基准左边，比基准大的移到右边。分区结束后，基准元素便落到了它的最终正确位置。
3. **递归求解**：对基准左、右两边的子序列分别递归进行快速排序。

#### 6.3 复杂度与稳定性
* **时间复杂度**：
  * **最好情况**：$O(n \log n)$，每次分区都非常均匀，正好二分。
  * **最坏情况**：$O(n^2)$，当序列已经有序或逆序，且每次选择边界元素作为基准时，分区退化为一维线性。
  * **平均情况**：$O(n \log n)$。
* **空间复杂度**：平均为 $O(\log n)$，最坏为 $O(n)$，主要取决于递归时的栈深度。
* **稳定性**：**不稳定**。分区过程中的长距离交换极易打乱相等元素的相对顺序。

#### 6.4 C++ 代码实现
```cpp
#include <iostream>
#include <algorithm>
using namespace std;

// 分区函数，采用区间末尾元素作为基准值
int par(int a[], int l, int r) {
    int piv = a[r]; 
    int i = l - 1;
    for (int j = l; j < r; j++) {
        if (a[j] < piv) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[r]);
    return i + 1; // 返回基准的最终落点
}

void srt_quick(int a[], int l, int r) {
    if (l >= r) return;
    int p = par(a, l, r);     // 划分
    srt_quick(a, l, p - 1);   // 递归排序左半部分
    srt_quick(a, p + 1, r);   // 递归排序右半部分
}

int main() {
    int a[] = {5, 2, 8, 1, 9, 4};
    int n = sizeof(a) / sizeof(a[0]);
    srt_quick(a, 0, n - 1);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
```

---

### 7. 堆排序 (Heap Sort)

#### 7.1 核心思想
堆排序利用了“堆（Heap）”这种数据结构。堆是一棵完全二叉树，大顶堆满足父节点的值总是大于或等于子节点。大顶堆的堆顶必然是整个树的最大值。

#### 7.2 算法步骤
1. **建堆（Build Heap）**：将无序序列调整构建成一个大顶堆。
2. **排序（Sort）**：
   * 将堆顶元素（最大值）与当前堆的最后一个元素交换，此时最大值已归位。
   * 堆的有效尺寸减 $1$。
   * 对新堆顶进行下沉调整（`heapify`），重新使其满足大顶堆性质。
   * 重复上述步骤，直到堆大小缩减为 $1$。

#### 7.3 复杂度与性质
* **时间复杂度**：始终为 $O(n \log n)$。建堆需要 $O(n)$ 复杂度，之后进行 $n-1$ 次调整，每次调整的时间开销为树的高度 $O(\log n)$。
* **空间复杂度**：$O(1)$，原地排序。
* **稳定性**：**不稳定**。在堆的重建和调整（上下游移动）过程中，相等元素的相对位置很容易发生变动。

#### 7.4 C++ 代码实现
```cpp
#include <iostream>
#include <algorithm>
using namespace std;

// 维护大顶堆的性质（下沉调整）
void hpf(int a[], int n, int i) {
    int lrg = i;       // 记录最大值的索引
    int l = 2 * i + 1; // 左孩子
    int r = 2 * i + 2; // 右孩子

if (l < n && a[l] > a[lrg]) lrg = l;
    if (r < n && a[r] > a[lrg]) lrg = r;

if (lrg != i) {
        swap(a[i], a[lrg]);
        hpf(a, n, lrg); // 递归调整受影响的子树
    }
}

void srt_heap(int a[], int n) {
    // 1. 构建大顶堆（自底向上进行调整）
    for (int i = n / 2 - 1; i >= 0; i--) {
        hpf(a, n, i);
    }

// 2. 逐个将堆顶最大值移至末尾，并重新维护堆
    for (int i = n - 1; i > 0; i--) {
        swap(a[0], a[i]); 
        hpf(a, i, 0); 
    }
}

int main() {
    int a[] = {5, 2, 8, 1, 9, 4};
    int n = sizeof(a) / sizeof(a[0]);
    srt_heap(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
```

---

## 三、 七大基于比较的排序算法小结

| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 | 备注与特点 |
| :--- | :---: | :---: | :---: | :---: | :---: | :--- |
| **冒泡排序** | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | **稳定** | 简单直观，优化版在已有序时极快 |
| **选择排序** | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 | 交换次数最少，性能与数据初始状态无关 |
| **插入排序** | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | **稳定** | 数据基本有序时性能接近线性，常用作小区间优化 |
| **希尔排序** | $O(n \log n) \sim O(n^{1.5})$ | $O(n^2)$ | $O(n \log n)$ | $O(1)$ | 不稳定 | 插入排序的改进版，突破了平方级障碍 |
| **归并排序** | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | **稳定** | 性能非常稳定，但有额外的线性内存开销 |
| **快速排序** | $O(n \log n)$ | $O(n^2)$ | $O(n \log n)$ | $O(\log n)$ | 不稳定 | 实际运行速度最快，若基准选择不佳性能易退化 |
| **堆排序** | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | 不稳定 | 原地排序，最坏性能同样为 $O(n \log n)$ |

我已为您将上述关于“基于比较的排序算法”的讲义内容进行了整理与深度优化。

在本次整理中，我完成了以下工作： 1. 消除了复制杂质：去除了所有代码块末尾残留的网页行号，并规范了原本由于复制导致的断行。 2. 规范化数学公式：使用标准 LaTeX 语法渲染了所有数组、算法复杂度（如 $O(n \log n)$、$O(n^2)$ 等）、以及排序比较与交换次数的推导公式。 3. 修复了代码中的逻辑错误： * 在“堆排序”的 main 函数中，原内容包含了一行多余且错误的 srt(a, 0, n - 1); 调用注释。我已将其精简移除，使 C++ 代码可直接编译运行。 4. 统一了小结表格：对最后一块的复杂度大表进行了排版对齐，使各算法的各项指标更加直观。

以下是整理后的完整 Markdown 内容：

基于比较的排序算法

在计算机科学中，排序（Sorting）是最基础且最重要的一类问题。简单来说，排序就是将一组杂乱无章的数据元素，按照某种预定的规则（例如，数值从小到大、字典序等）重新排列成一个有序序列的过程。

例如，给定一个整数数组 $A = {5, 2, 8, 1, 9}$，我们希望将其按照从小到大的顺序排序，得到的结果将是 $B = {1, 2, 5, 8, 9}$。这个从数组 $A$ 到数组 $B$ 的过程，就是一个排序过程。

一、排序算法的性能衡量指标

排序算法的优劣通常由其运行效率来衡量，主要体现在以下三个方面：

时间复杂度（Time Complexity）：算法执行所需的时间，通常通过比较次数和交换次数（或移动次数）来衡量。
空间复杂度（Space Complexity）：算法执行过程中额外占用的内存空间。
稳定性（Stability）：指在待排序的序列中，若存在多个具有相同关键字的元素，经过排序后，这些元素的原有相对顺序保持不变。
定义：设序列中存在两个元素 $a$ 和 $b$，它们的关键字相同（即 $key(a) = key(b)$），且在排序前 $a$ 在 $b$ 前面。若排序后 $a$ 仍然在 $b$ 的前面，则该排序算法是稳定的；反之，若相对位置可能发生改变，则称该算法是不稳定的。

排序算法的两大门派

比较类排序：通过比较元素之间的关键字大小来决定元素的相对次序。其时间复杂度的理论下限是 $O(n \log n)$。常见的比较类排序有冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序和堆排序。
非比较类排序：不通过比较来确定元素顺序，而是利用元素自身的特性（如数值范围、位数等）来进行排序，可以突破 $O(n \log n)$ 的下限达到线性时间 $O(n)$。常见的有计数排序、基数排序和桶排序。

本节重点介绍基于比较的排序算法。

二、七大基于比较的排序算法详解

1. 冒泡排序 (Bubble Sort)

1.1 核心思想

通过重复地遍历待排序序列，依次比较相邻的两个元素。如果它们的顺序错误（如前一个比后一个大），就交换它们。

这个过程会一直重复，直到在某一次遍历中没有发生任何元素交换，这意味着整个序列已经变得有序。在从小到大排序的过程中，较小的元素会经过交换慢慢地“浮”到序列的顶部，而较大的元素则会“沉”到序列的底部。

1.2 分步图解

假设待排序数组为 $A = {6, 5, 3, 1, 8, 7, 2, 4}$。

第一趟：目标是将当前序列的最大值 $8$ 移动到最后。
比较 $A[0]$ 和 $A[1]$（$6$ 和 $5$）。$6 > 5$，交换。序列变为 ${5, 6, 3, 1, 8, 7, 2, 4}$。
比较 $A[1]$ 和 $A[2]$（$6$ 和 $3$）。$6 > 3$，交换。序列变为 ${5, 3, 6, 1, 8, 7, 2, 4}$。
比较 $A[2]$ 和 $A[3]$（$6$ 和 $1$）。$6 > 1$，交换。序列变为 ${5, 3, 1, 6, 8, 7, 2, 4}$。
比较 $A[3]$ 和 $A[4]$（$6$ 和 $8$）。$6 < 8$，不交换。序列不变。
比较 $A[4]$ 和 $A[5]$（$8$ 和 $7$）。$8 > 7$，交换。序列变为 ${5, 3, 1, 6, 7, 8, 2, 4}$。
比较 $A[5]$ 和 $A[6]$（$8$ 和 $2$）。$8 > 2$，交换。序列变为 ${5, 3, 1, 6, 7, 2, 8, 4}$。
比较 $A[6]$ 和 $A[7]$（$8$ 和 $4$）。$8 > 4$，交换。序列变为 ${5, 3, 1, 6, 7, 2, 4, 8}$。
结果：第一趟结束，最大元素 $8$ 已经“沉”到了数组末尾。
第二趟：目标是将剩余 $n-1$ 个元素中的最大值 $7$ 移动到倒数第二位，比较范围缩减为 $A[0]$ 到 $A[6]$。
比较 $5$ 和 $3$ $\to$ 交换 $\to$ ${3, 5, 1, 6, 7, 2, 4, 8}$
比较 $5$ 和 $1$ $\to$ 交换 $\to$ ${3, 1, 5, 6, 7, 2, 4, 8}$
比较 $5$ 和 $6$ $\to$ 不交换
比较 $6$ 和 $7$ $\to$ 不交换
比较 $7$ 和 $2$ $\to$ 交换 $\to$ ${3, 1, 5, 6, 2, 7, 4, 8}$
比较 $7$ 和 $4$ $\to$ 交换 $\to$ ${3, 1, 5, 6, 2, 4, 7, 8}$
结果：次大元素 $7$ 就位。

1.3 优化思路

如果在某一趟遍历中，没有发生任何一次交换，说明整个序列已经完全有序，可提前结束排序。例如对有序数组进行检验，或提前排好序时直接跳出。

1.4 C++ 代码实现

基础版本

#include <iostream>
#include <algorithm>
using namespace std;

void bub(int a[], int n) {
    // 外层循环控制趟数
    for (int i = 0; i < n - 1; ++i) {
        // 内层循环负责每趟的相邻元素比较
        // 因为末尾 i 个元素已有序，故上界为 n - 1 - i
        for (int j = 0; j < n - 1 - i; ++j) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
            }
        }
    }
}

int main() {
    int a[] = {6, 5, 3, 1, 8, 7, 2, 4};
    int n = sizeof(a) / sizeof(a[0]);
    bub(a, n);
    for (int i = 0; i < n; ++i) cout << a[i] << " ";
    cout << endl;
    return 0;
}

优化版本（加入交换标志位）

#include <iostream>
#include <algorithm>
using namespace std;

void bub_optimized(int a[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        bool flg = false; // 默认为 false 表示未发生交换
        for (int j = 0; j < n - 1 - i; ++j) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                flg = true; // 发生了交换
            }
        }
        // 若此趟遍历无任何交换，说明已有序，直接提前退出
        if (!flg) break;
    }
}

int main() {
    int a[] = {1, 2, 3, 5, 4};
    int n = sizeof(a) / sizeof(a[0]);
    bub_optimized(a, n);
    for (int i = 0; i < n; ++i) cout << a[i] << " ";
    cout << endl;
    return 0;
}

1.5 复杂度与性质详解

比较次数：无论初始状态如何，基础版本的总比较次数 $C(n)$ 为恒定值： $$C(n) = (n-1) + (n-2) + \dots + 1 = \sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = O(n^2)$$ 优化版本在最好情况（已排序）下只需比较 $n-1$ 次，即 $O(n)$。
交换次数：
最坏情况（完全逆序）： $$S_{max}(n) = \frac{n(n-1)}{2} = O(n^2)$$
最好情况（已有序）：$0$ 次。
平均情况：随机序列的平均交换次数约为 $\frac{n(n-1)}{4}$，仍属于 $O(n^2)$。
稳定性：稳定。只有在满足 $a[j] > a[j+1]$ 的严格不等式时才发生交换，元素相等时不交换，因此相等元素的相对顺序不会发生改变。
空间复杂度：$O(1)$，原地排序。

2. 选择排序 (Selection Sort)

2.1 核心思想

每一轮在未排序的序列中找到最小（或最大）的元素，然后将其放置到已排序序列的末尾。

2.2 算法步骤

在未排序序列 $A[0 \dots n-1]$ 中找到最小元素，与 $A[0]$ 交换。
在未排序序列 $A[1 \dots n-1]$ 中找到最小元素，与 $A[1]$ 交换。
重复此过程，直到剩下最后一个元素，排序完毕。

2.3 复杂度与性质

时间复杂度：始终为 $O(n^2)$。比较次数与初始排列无关，必须完整执行两重循环。
空间复杂度：$O(1)$，原地排序。
稳定性：不稳定。例如序列 ${5_a, 8, 5_b, 2, 9}$，第一轮找到最小值 $2$，与首位 $5_a$ 交换后变为 ${2, 8, 5_b, 5_a, 9}$，两个 $5$ 的相对顺序发生了改变。

2.4 C++ 代码实现

#include <iostream>
#include <algorithm>
using namespace std;

void sel(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i; // 记录当前轮次最小元素的索引
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            swap(a[i], a[min_idx]);
        }
    }
}

int main() {
    int a[] = {5, 2, 8, 1, 9, 4};
    int n = sizeof(a) / sizeof(a[0]);
    sel(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

3. 插入排序 (Insertion Sort)

3.1 核心思想

将待排序序列分为“已排序”和“未排序”两部分。每次从未排序部分取出一个元素，插入到已排序部分的正确位置。

3.2 算法步骤

将第一个元素视为初始的已排序序列。
从第二个元素开始，作为待插入元素 cur。
将 cur 与已排序序列中的元素从后向前依次比较。
若已排序元素大于 cur，则将该元素向后移动一位。
重复移动，直至找到小于或等于 cur 的位置，将 cur 插入。

3.3 复杂度与性质

时间复杂度：
最好情况：$O(n)$，当序列已经有序时，内层循环只比较一次就停止，无需移动。
最坏情况：$O(n^2)$，序列完全逆序。
平均情况：$O(n^2)$。
空间复杂度：$O(1)$，原地排序。
稳定性：稳定。移动元素时只有在严格大于 cur 时才向后移，若相等则停止移动，故不会打乱相对位置。

3.4 C++ 代码实现

#include <iostream>
using namespace std;

void ins(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int cur = a[i]; // 待插入元素
        int j = i - 1;
        // 在已排序部分 a[0...i-1] 中寻找插入位置
        while (j >= 0 && a[j] > cur) {
            a[j + 1] = a[j]; // 元素后移
            j--;
        }
        a[j + 1] = cur; // 插入
    }
}

int main() {
    int a[] = {5, 2, 8, 1, 9, 4};
    int n = sizeof(a) / sizeof(a[0]);
    ins(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

4. 希尔排序 (Shell Sort)

4.1 核心思想

希尔排序是插入排序的一种高效改进版本。它通过将整个序列按某个“增量” gap 分成若干个子序列，对每个子序列分别进行直接插入排序。随着增量逐渐减小直至 gap = 1，序列已基本有序，最后再进行一次常规插入排序，效率将非常高。

4.2 算法步骤

选择一个增量序列（常用初始增量为 $gap = n/2$，每次减半）。
根据当前的 gap，将序列分为 gap 个子序列，子序列内的元素物理间距为 gap。
对这些子序列分别进行直接插入排序。
减小增量 gap，重复上述步骤。
直到 $gap = 1$，对全体元素进行最后一次插入排序。

4.3 复杂度与性质

时间复杂度：依赖于增量序列的选择。
平均情况下一般在 $O(n \log n)$ 到 $O(n^{1.5})$ 之间。
最坏情况若使用除 2 减半的序列，仍为 $O(n^2)$。
空间复杂度：$O(1)$。
稳定性：不稳定。在分组子序列交叉进行排序时，相同关键字的元素可能被划分到不同子序列中，发生跨越式交换，导致相对顺序被打乱。

4.4 C++ 代码实现

#include <iostream>
using namespace std;

void shl(int a[], int n) {
    // 增量 gap 从 n/2 开始，每次减半
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个子序列进行插入排序
        for (int i = gap; i < n; i++) {
            int cur = a[i];
            int j = i - gap;
            while (j >= 0 && a[j] > cur) {
                a[j + gap] = a[j];
                j -= gap;
            }
            a[j + gap] = cur;
        }
    }
}

int main() {
    int a[] = {5, 2, 8, 1, 9, 4, 3, 7, 6};
    int n = sizeof(a) / sizeof(a[0]);
    shl(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

5. 归并排序 (Merge Sort)

5.1 核心思想

归并排序是分治法（Divide and Conquer）的典型应用。其基本思路是“先递归分解，再双指针合并结果”。

5.2 算法步骤

分解（Divide）：将当前序列从中间对半切分，递归执行，直至子序列长度为 $1$。
合并（Combine）：将相邻的两个有序子序列合并成一个更大的有序序列。使用双指针分别指向两个子序列头部，挑选较小的元素放入临时数组，最后将临时数组写回原数组。

5.3 复杂度与性质

时间复杂度：始终为 $O(n \log n)$。分解层数为 $\log_2 n$ 层，每层合并的开销是线性的 $O(n)$。性能极为稳定，不受初始数据形态影响。
空间复杂度：$O(n)$，合并过程中需要开辟与待合并元素总数等长的辅助空间。
稳定性：稳定。在合并过程中，若遇两个元素相等，我们规定优先把第一个子序列中的元素拷入临时数组，即可完美保证稳定性。

5.4 C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

// 合并两个有序区间 a[l...m] 和 a[m+1...r]
void mrg(int a[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    vector<int> L(n1), R(n2); 

    for (int i = 0; i < n1; i++) L[i] = a[l + i];
    for (int j = 0; j < n2; j++) R[j] = a[m + 1 + j];

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            a[k++] = L[i++];
        } else {
            a[k++] = R[j++];
        }
    }
    while (i < n1) a[k++] = L[i++];
    while (j < n2) a[k++] = R[j++];
}

void srt_merge(int a[], int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2; // 二分
    srt_merge(a, l, m);
    srt_merge(a, m + 1, r);
    mrg(a, l, m, r);         // 合并
}

int main() {
    int a[] = {5, 2, 8, 1, 9, 4};
    int n = sizeof(a) / sizeof(a[0]);
    srt_merge(a, 0, n - 1);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

6. 快速排序 (Quick Sort)

6.1 核心思想

同样基于分治法。它通过一趟划分将待排记录分隔成独立的两部分，使得其中一部分的所有数据都比另一部分小。然后，递归地对这两部分数据继续进行快速排序。

6.2 算法步骤

选择基准（Pivot）：从序列中选出一个元素作为基准。
分区（Partition）：通过交换，将所有比基准小的元素移到基准左边，比基准大的移到右边。分区结束后，基准元素便落到了它的最终正确位置。
递归求解：对基准左、右两边的子序列分别递归进行快速排序。

6.3 复杂度与稳定性

时间复杂度：
最好情况：$O(n \log n)$，每次分区都非常均匀，正好二分。
最坏情况：$O(n^2)$，当序列已经有序或逆序，且每次选择边界元素作为基准时，分区退化为一维线性。
平均情况：$O(n \log n)$。
空间复杂度：平均为 $O(\log n)$，最坏为 $O(n)$，主要取决于递归时的栈深度。
稳定性：不稳定。分区过程中的长距离交换极易打乱相等元素的相对顺序。

6.4 C++ 代码实现

#include <iostream>
#include <algorithm>
using namespace std;

// 分区函数，采用区间末尾元素作为基准值
int par(int a[], int l, int r) {
    int piv = a[r]; 
    int i = l - 1;
    for (int j = l; j < r; j++) {
        if (a[j] < piv) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[r]);
    return i + 1; // 返回基准的最终落点
}

void srt_quick(int a[], int l, int r) {
    if (l >= r) return;
    int p = par(a, l, r);     // 划分
    srt_quick(a, l, p - 1);   // 递归排序左半部分
    srt_quick(a, p + 1, r);   // 递归排序右半部分
}

int main() {
    int a[] = {5, 2, 8, 1, 9, 4};
    int n = sizeof(a) / sizeof(a[0]);
    srt_quick(a, 0, n - 1);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

7. 堆排序 (Heap Sort)

7.1 核心思想

堆排序利用了“堆（Heap）”这种数据结构。堆是一棵完全二叉树，大顶堆满足父节点的值总是大于或等于子节点。大顶堆的堆顶必然是整个树的最大值。

7.2 算法步骤

建堆（Build Heap）：将无序序列调整构建成一个大顶堆。
排序（Sort）：
将堆顶元素（最大值）与当前堆的最后一个元素交换，此时最大值已归位。
堆的有效尺寸减 $1$。
对新堆顶进行下沉调整（heapify），重新使其满足大顶堆性质。
重复上述步骤，直到堆大小缩减为 $1$。

7.3 复杂度与性质

时间复杂度：始终为 $O(n \log n)$。建堆需要 $O(n)$ 复杂度，之后进行 $n-1$ 次调整，每次调整的时间开销为树的高度 $O(\log n)$。
空间复杂度：$O(1)$，原地排序。
稳定性：不稳定。在堆的重建和调整（上下游移动）过程中，相等元素的相对位置很容易发生变动。

7.4 C++ 代码实现

#include <iostream>
#include <algorithm>
using namespace std;

// 维护大顶堆的性质（下沉调整）
void hpf(int a[], int n, int i) {
    int lrg = i;       // 记录最大值的索引
    int l = 2 * i + 1; // 左孩子
    int r = 2 * i + 2; // 右孩子

    if (l < n && a[l] > a[lrg]) lrg = l;
    if (r < n && a[r] > a[lrg]) lrg = r;

    if (lrg != i) {
        swap(a[i], a[lrg]);
        hpf(a, n, lrg); // 递归调整受影响的子树
    }
}

void srt_heap(int a[], int n) {
    // 1. 构建大顶堆（自底向上进行调整）
    for (int i = n / 2 - 1; i >= 0; i--) {
        hpf(a, n, i);
    }

    // 2. 逐个将堆顶最大值移至末尾，并重新维护堆
    for (int i = n - 1; i > 0; i--) {
        swap(a[0], a[i]); 
        hpf(a, i, 0); 
    }
}

int main() {
    int a[] = {5, 2, 8, 1, 9, 4};
    int n = sizeof(a) / sizeof(a[0]);
    srt_heap(a, n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

三、七大基于比较的排序算法小结

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性	备注与特点
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定	简单直观，优化版在已有序时极快
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	交换次数最少，性能与数据初始状态无关
插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定	数据基本有序时性能接近线性，常用作小区间优化
希尔排序	$O(n \log n) \sim O(n^{1.5})$	$O(n^2)$	$O(n \log n)$	$O(1)$	不稳定	插入排序的改进版，突破了平方级障碍
归并排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	稳定	性能非常稳定，但有额外的线性内存开销
快速排序	$O(n \log n)$	$O(n^2)$	$O(n \log n)$	$O(\log n)$	不稳定	实际运行速度最快，若基准选择不佳性能易退化
堆排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	不稳定	原地排序，最坏性能同样为 $O(n \log n)$

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com