1. 冒泡排序（Bubble Sort）

结论速描：通过不断比较相邻元素并交换，把“最大的”元素逐步移到右端（或最小的移到左端）。简单、稳定，但效率低。

直观想法

想象你在把一列数排队，每次从左到右看一对相邻的人，如果前面的人比后面的大就让他们换位置。这样每次完整扫描，队伍里最大的那个人会慢慢“冒泡”到队尾。下一轮再从头到尾扫描，但可以忽略已经到尾部的已排序元素。

步骤举例

数组 [5, 3, 4, 1]：

• 第一轮比较并交换相邻对：

  • 比 5 和 3 → 交换 → [3,5,4,1]
  • 比 5 和 4 → 交换 → [3,4,5,1]
  • 比 5 和 1 → 交换 → [3,4,1,5]（5 已到正确位置）

• 第二轮只看前三个元素：

  • 3 vs 4 → 不交换
  • 4 vs 1 → 交换 → [3,1,4,5]

• 第三轮：

  • 3 vs 1 → 交换 → [1,3,4,5]

不变式 & 正确性直观证据

每完成第 k 轮，右边 k 个元素是全局第 n-k+1 … n 的最大元素，且按顺序。递归使用此不变式能证明最终有序。

复杂度来源

每轮最多做 O(n) 次比较，最多需要 n 轮 → O(n²)。最好的情况（已排序）可以用 swapped 标志提前停止 → O(n)。

常见优化与变种

• 提前退出（若一轮无交换则结束）。
• 双向冒泡（Cocktail shaker）：从两端来回，缩短移动距离。
• 并不用于实际大型排序，常用于教学或检测小数组。

稳定性与内存/并行

• 稳定（相等元素不改变相对顺序，若实现为仅在 > 时交换）。
• 原地，O(1) 额外内存。
• 并行化不合适（高度串行）。

复杂度

情况	时间复杂度	空间	稳定性
最好	O(n)	O(1)	稳定
最坏	O(n²)	O(1)

实现

void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    bool swapped;
    for (int i = 0; i < n - 1; ++i) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // 提前结束
    }
}

---

2. 选择排序（Selection Sort）

结论速描：每次在未排序部分找到最小（或最大）元素，放到已排序部分末尾。简单但不稳定（默认交换会破坏相对顺序），亦 O(n²)。

直观想法

把数组分成“已排序前缀”和“未排序后缀”。每次在未排序部分扫描找到最小元素，把它放到前缀后面。与冒泡不同，它不依赖相邻交换——找到最小一次性放到正确位置。

步骤举例

[4,2,3,1]：

• 找到全数组的最小 1，交换到索引 0 → [1,2,3,4]
• 接着在剩下元素中找最小（2），交换到索引1（已经是）……最终完成。

不变式

每轮结束时前缀是全局最小的 k 个元素且位置确定。

复杂度说明

每轮找最小需要 O(n-k) 次比较，共 O(n²)。交换次数≤n（比冒泡少），但交换可能把相等元素的相对顺序打乱→不稳定。

优化/变种

• 双端选择（同时找最小与最大，放两端）能把轮数减半。
• 适合内存写代价高场景（交换次数少）。

稳定性/内存/并行

• 不稳定（交换会改变顺序）；可通过稳定实现（使用链表或稳定输出数组）变为稳定但需要额外空间。
• O(1) 额外空间。
• 并行化意义不大。

复杂度

情况	时间复杂度	空间	稳定性
所有	O(n²)	O(1)	不稳定

实现

void selectionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j)
            if (arr[j] < arr[minIndex]) minIndex = j;
        if (i != minIndex) std::swap(arr[i], arr[minIndex]);
    }
}

---

3. 插入排序（Insertion Sort）

结论速描：维护左侧已排序序列，把当前元素插入到合适位置。对近乎有序或小数组非常快，稳定，常用于混合排序的底层（比如快速排序小区间切换）。

直观想法

想象你手里抓一张牌一张牌插入到已经排好的手牌中：每次将新的牌与已排序的从右到左比较，找到位置插入。对于每个元素只移动比它大的元素一格。

步骤举例

[3,1,4,2]

• i=1: 插 1 到前面 → [1,3,4,2]
• i=2: 插 4 → 不动
• i=3: 插 2 → 移动 4 和 3 → [1,2,3,4]

不变式

在处理第 i 个元素前，前 i-1 个元素是有序的。插入操作在保持不变式的前提下结束。

复杂度说明

最坏情形（逆序）需要移动 O(i) 步，对所有 i 累计 O(n²)。最好情况（已排序）只有一次比较/插入 → O(n)。因此插入排序是自适应的，对接近有序的数据优秀。

优化/变种

• 二分插入：用二分查找位置减少比较到 O(log n)，但移动元素仍需 O(n)。
• 使用链表降低移动开销（但随机访问代价高）。
• 用作小规模数组的内联排序（比如 std::sort 的阈值切换）。

稳定性/内存/并行

• 稳定（插入时保持同值元素原相对顺序）。
• 原地，O(1) 额外空间。
• 并行化不常用。

复杂度

情况	时间复杂度	空间	稳定性
最好	O(n)	O(1)	✅ 稳定
最坏	O(n²)	O(1)

实现

void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

---

4. 希尔排序（Shell Sort）

结论速描：分组进行插入排序：先比较相距 gap 的元素（组内插入），逐步缩小 gap，最终 gap=1 时完成普通插入。通过减少移动距离（“先粗后细”）提升性能。

直观想法

把数组分成 gap 个子序列（按下标模 gap 划分），每个子序列执行插入排序。首次 gap 很大，把远距离的元素就位，后来 gap 减小，局部更有序，因此最终插入排序时元素已经很接近目标位置，从而减少整体移动。

步骤与例子

常见 gap 序列：n/2, n/4, ..., 1（Knuth、Hibbard、Sedgewick 等序列有更好表现）。例如 [8,9,1,7,2,3,5,4] 用 gap=4 做 4 组插入，再 gap=2，再 gap=1。

不变式与直观正确性

每次 gap 排序使得跨 gap 的顺序被修正，最终 gap=1 时等价于一次插入排序但此时数组接近有序，插入排序成本减少。

复杂度说明

复杂度依赖 gap 序列：最坏可能接近 O(n²)，但合适序列（如 Sedgewick）能达到近 O(n^{4/3})、或实测接近 O(n log^2 n)。精确界是复杂的；不过在实践上希尔排序对中等规模数组很高效。

优化/变种

• 选好 gap 序列（Knuth、Sedgewick、Tokuda 等）。
• P线程化：可以对不同 gap 子序列并行排序（注意 cache 与访问冲突）。

稳定性/内存/并行

• 不稳定（相等元素可能跨组移动）。
• 原地，O(1) 额外空间。
• 并行化有限但可在大型数组中用分块并行。

复杂度

情况	时间复杂度	空间	稳定性
平均	O(n log n)	O(1)	❌ 不稳定

实现

void shellSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            int temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

---

5. 归并排序（Merge Sort）

结论速描：分治：递归把数组分为两半，分别排序后合并。稳定、时间复杂度稳定 O(n log n)，但需要 O(n) 额外空间（标准实现）。

直观想法

将问题分解成两个规模约为 n/2 的子问题，分别排序，再把两个已排序数组按“归并（像合并两组扑克牌）”的方式生成有序数组。核心操作是线性时间合并。

步骤举例

[5,2,4,7,1,3,6]：

• 递归拆分直到大小 1
• 合并大小为 1 的子序列变为 2、有序子序列，以此类推直到恢复原大小

不变式与正确性

合并两个已排序数组输出的每一步选择当前两端较小值放到输出，保证输出有序且保持稳定性（当相等时先取左边保证稳定）。由归纳法证明正确性：单元素序列为有序，合并保有序，递归合并全局有序。

复杂度来源

划分深度为 log₂ n（每层合并处理 n 个元素）→ O(n log n)。额外空间来自合并缓冲数组为 O(n)。

优化/变种

• 自底向上（迭代）归并（减少递归开销）。
• 原地归并（复杂，通常 O(n log n) 时间，或用旋转技术）：实践中较少用。
• 使用外部归并（外排序）处理数据过大无法放入内存场景。
• 稳定归并的并行化非常容易：不同段可并行排序，合并可用并行技术。

稳定性/内存/并行

• 稳定（如实现保留相等元素的先后顺序）。
• 额外空间 O(n)（可以用小常数块优化内存拷贝）。
• 非常适合并行（线程/分布式合并）。

---

复杂度

情况	时间复杂度	空间	稳定性
所有	O(n log n)	O(n)	✅ 稳定

实现

void merge(std::vector<int>& arr, int l, int m, int r) {
    std::vector<int> left(arr.begin() + l, arr.begin() + m + 1);
    std::vector<int> right(arr.begin() + m + 1, arr.begin() + r + 1);
    int i = 0, j = 0, k = l;
    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) arr[k++] = left[i++];
        else arr[k++] = right[j++];
    }
    while (i < left.size()) arr[k++] = left[i++];
    while (j < right.size()) arr[k++] = right[j++];
}

void mergeSort(std::vector<int>& arr, int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
}

---

6. 快速排序（Quick Sort）

结论速描：通过「划分（partition）」把数组按 pivot 分成两边，再递归排序两边。实用性强，平均 O(n log n)，但最坏 O(n²)（比如已排序加差的 pivot 选择）。现代实现（Introsort/两枢轴）是 std::sort 的基础。

直观想法

任选一个枢轴元素（pivot），把数组重排为：小于 pivot 的在左，等于（或部分）中间，大于在右。pivot 划分后，它处在正确位置。对左右两部分递归完成排序。关键是如何选 pivot 与如何高效做 partition。

步骤举例（Lomuto / Hoare partition）

• Hoare partition 更少交换：两个指针从两端向中间推进，遇到逆序就交换。
• Lomuto partition（简单但在某些情况下慢）：使用一个边界来分割小元素。

不变式与正确性

每次 partition 完成后 pivot 放在最终位置；左侧所有元素 ≤ pivot、右侧 ≥ pivot。递归应用保证全局排序。

复杂度来源

如果每次划分接近均匀，递归深度 log n，每层比较 ~n → O(n log n)。若每次都划分极不均匀（如始终把最小元素作为 pivot），深度 n，比较量为 O(n²)。

优化/变种（非常多）

• 随机化 pivot（随机选择或 shuffle）降低最坏概率。
• 三数取中（median-of-three）选择 pivot。
• 双枢轴 quicksort（Yaroslavskiy dual-pivot used in Java）提高常数性能。
• 切换到插入排序处理小子数组（阈值如 16）。
• 防止递归深度过大：限制递归深度或转换为 Introsort（当递归深度超过 log n 的常数倍时改用堆排序，保证最坏 O(n log n)）。这就是 std::sort 的做法。

稳定性/内存/并行

• 标准 quicksort 非稳定（相等顺序可能改变）；可通过额外缓冲实现稳定版本但需额外内存。
• 原地（可做到 O(log n) 额外栈空间）。
• 并行化：左右子数组可并行排序（并行 quicksort 经常用于多核）。

---

复杂度

情况	时间复杂度	空间	稳定性
最好	O(n log n)	O(log n)	❌ 不稳定
最坏	O(n²)	O(log n)

实现

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; ++j) {
        if (arr[j] < pivot)
            std::swap(arr[++i], arr[j]);
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

---