常用排序算法与快速选择¶

排序算法是计算机科学与算法竞赛中最基石的算法族之一。除直接对序列重排外，排序更常作为贪心、双指针、二分搜索、离散化、凸包扫描（Graham 扫描法）以及区间问题的前置必要步骤。

1. 比较类排序的理论下界¶

对于任意基于元素两两比较（Comparison-Based）的排序算法，其最坏时间复杂度不可能低于 \(\mathcal{O}(N \log N)\)。

决策树模型证明 (Decision Tree Lower Bound)¶

任何比较排序算法在执行时，都可以建模为一棵二叉决策树（Decision Tree）：

内部节点（Internal Node）：代表一次形如 \(A[i] \le A[j]\) 的比较，根据真/假产生左、右两条分支；
叶子节点（Leaf Node）：代表输入元素经过一系列比较后得到的一个唯一确定的排列顺序。

对于包含 \(N\) 个互异元素的数组，其所有可能的排列总数为全排列数 \(N!\)。为了保证对任意输入都能正确排序，决策树的叶子节点总数 \(L\) 必须满足：

\[ L \ge N! \]

高度为 \(h\) 的二叉树最多拥有 \(2^h\) 个叶子节点，因此：

\[ 2^h \ge L \ge N! \implies h \ge \log_2(N!) \]

决策树的高度 \(h\) 恰好对应算法在最坏情况下所需的最大比较次数。根据斯特林近似公式（Stirling's Approximation） \(\ln(N!) \approx N \ln N - N + \mathcal{O}(\log N)\)，我们有：

\[ h \ge \log_2(N!) = \sum_{i=1}^{N} \log_2 i \ge \sum_{i=\lceil N/2 \rceil}^{N} \log_2 \left(\frac{N}{2}\right) \ge \frac{N}{2} (\log_2 N - 1) = \Omega(N \log N) \]

因此，任何基于比较的排序算法在最坏情况下的比较次数理论下界为 \(\Omega(N \log N)\)。若想突破 \(\mathcal{O}(N \log N)\) 的瓶颈，必须依赖非比较类算法（如基数排序、计数排序或桶排序），利用数值本身的位特征或值域分布。

2. 常用排序算法全景对比¶

算法名称	最好时间	平均时间	最坏时间	空间复杂度	稳定性	核心特征与竞赛场景
快速排序 (Quick Sort)	\(\mathcal{O}(N \log N)\)	\(\mathcal{O}(N \log N)\)	\(\mathcal{O}(N^2)\)	\(\mathcal{O}(\log N)\)	不稳定	缓存命中率极高，常数极小，工业与竞赛默认首选
归并排序 (Merge Sort)	\(\mathcal{O}(N \log N)\)	\(\mathcal{O}(N \log N)\)	\(\mathcal{O}(N \log N)\)	\(\mathcal{O}(N)\)	稳定	分治典范，求逆序对、外部排序、链表排序最佳方案
堆排序 (Heap Sort)	\(\mathcal{O}(N \log N)\)	\(\mathcal{O}(N \log N)\)	\(\mathcal{O}(N \log N)\)	\(\mathcal{O}(1)\)	不稳定	严格原地排序，防快排退化（内省排序组件）
插入排序 (Insertion Sort)	\(\mathcal{O}(N)\)	\(\mathcal{O}(N^2)\)	\(\mathcal{O}(N^2)\)	\(\mathcal{O}(1)\)	稳定	小规模数据（\(N \le 16 \sim 32\)）常数极快
计数排序 (Counting Sort)	\(\mathcal{O}(N + K)\)	\(\mathcal{O}(N + K)\)	\(\mathcal{O}(N + K)\)	\(\mathcal{O}(K)\)	稳定	值域 \(K\) 较小（如字符集或小整数）时线性耗时
基数排序 (Radix Sort)	\(\mathcal{O}(d(N + R))\)	\(\mathcal{O}(d(N + R))\)	\(\mathcal{O}(d(N + R))\)	\(\mathcal{O}(N + R)\)	稳定	32/64位整数极致卡常，常数比 `std::sort` 快 2~4 倍
桶排序 (Bucket Sort)	\(\mathcal{O}(N)\)	\(\mathcal{O}(N + K)\)	\(\mathcal{O}(N^2)\)	\(\mathcal{O}(N + K)\)	稳定	数据均匀分布时达线性，常结合抽屉原理证明最值

3. 快速排序与快速选择 (Quick Sort & Quickselect)¶

快速排序由 Tony Hoare 提出，采用分治（Divide and Conquer）策略。其关键步骤在于划分（Partition）：选取一个基准值（Pivot），将序列划分为两部分，左侧所有元素均不大于 Pivot，右侧所有元素均不小于 Pivot，然后递归处理子区间。

3.1 常见退化陷阱与防范¶

单调/近乎有序退化：若固定选取第一个或最后一个元素作为基准，在面对升序、降序或构造出的单调攻击用例（Anti-quicksort tests）时，每次只能排除一个元素，递归深度退化为 \(\mathcal{O}(N)\)，总时间退化为 \(\mathcal{O}(N^2)\)。
- 对策：采用随机化基准（Randomized Pivot）或三数取中法（Median-of-three）。
全相同元素退化：若使用单向扫描（Lomuto Partition），当数组包含大量重复元素时，相等元素全部被划分到某一侧，导致子问题极度不均衡，时间复杂度同样劣化至 \(\mathcal{O}(N^2)\)（LeetCode 912 包含了全 0 测试用例）。
- 对策：采用双路快速排序（Hoare 双向逼近）或三路快速排序（Dutch National Flag 三路划分）。

3.2 竞赛级双路快速排序模板 (Hoare Partition + 随机化)¶

双路快排在左右两端各设置一个指针向中间靠拢，左右指针分别停在 >= pivot 和 <= pivot 的位置，从而使与 Pivot 相等的元素均匀分布在两侧，避免退化。

#include <vector>
#include <random>
#include <chrono>
#include <algorithm>

class QuickSort {
private:
    static inline std::mt19937 rng{
        static_cast<std::mt19937::result_type>(
            std::chrono::steady_clock::now().time_since_epoch().count()
        )
    };

    template <typename T>
    static void sort_internal(std::vector<T> &a, int l, int r) {
        if (l >= r) return;

        // 随机选择基准元并交换到首位
        std::uniform_int_distribution<int> dist(l, r);
        std::swap(a[l], a[dist(rng)]);
        T pivot = a[l];

        // Hoare 双向双指针划分
        int i = l - 1, j = r + 1;
        while (true) {
            do { ++i; } while (a[i] < pivot);
            do { --j; } while (a[j] > pivot);
            if (i >= j) break;
            std::swap(a[i], a[j]);
        }

        // 此时 a[l...j] <= pivot, a[j+1...r] >= pivot
        sort_internal(a, l, j);
        sort_internal(a, j + 1, r);
    }

public:
    template <typename T>
    static void sort(std::vector<T> &a) {
        sort_internal(a, 0, static_cast<int>(a.size()) - 1);
    }
};

3.3 三路快速排序模板 (Three-Way Quick Sort)¶

将数组严格划分为三段：\([l, lt-1]\) 为严格小于 Pivot 的部分，\([lt, gt]\) 为等于 Pivot 的部分，\([gt+1, r]\) 为严格大于 Pivot 的部分。递归时完全跳过相等的中间段。在面对包含大量重复数值的数据集时，时间复杂度可大幅优化至 \(\mathcal{O}(N)\)。

#include <vector>
#include <random>
#include <chrono>
#include <algorithm>

template <typename T>
void quick_sort_3way(std::vector<T> &a, int l, int r) {
    if (l >= r) return;

    static std::mt19937 rng{
        static_cast<std::mt19937::result_type>(
            std::chrono::steady_clock::now().time_since_epoch().count()
        )
    };
    std::uniform_int_distribution<int> dist(l, r);
    std::swap(a[l], a[dist(rng)]);
    T pivot = a[l];

    int lt = l;      // a[l...lt-1] < pivot
    int gt = r;      // a[gt+1...r] > pivot
    int i = l + 1;   // a[lt...i-1] == pivot

    while (i <= gt) {
        if (a[i] < pivot) {
            std::swap(a[lt++], a[i++]);
        } else if (a[i] > pivot) {
            std::swap(a[i], a[gt--]); // 此处 i 不自增，需继续检验交换过来的新元素
        } else {
            ++i;
        }
    }

    // 递归处理严格小于和严格大于的两个子区间
    quick_sort_3way(a, l, lt - 1);
    quick_sort_3way(a, gt + 1, r);
}

3.4 快速选择算法 (Quickselect / Introselect)¶

快速选择算法用于在线性期望时间内寻找无序序列中第 \(K\) 小（或第 \(K\) 大）的元素。在划分后，只需进入包含目标排名 \(K\) 的单侧子区间继续递归：

\[ T(N) = T(N/2) + \mathcal{O}(N) \implies T(N) = \mathcal{O}(N) \]

其最坏情况可能退化为 \(\mathcal{O}(N^2)\)。C++ 标准库中的 std::nth_element 采用内省选择算法（Introselect），在递归过深时切换为 BFPRT 线性中位数算法或堆选择，确保最坏情况严格 \(\mathcal{O}(N)\)。

#include <vector>
#include <random>
#include <chrono>
#include <algorithm>

// 查找数组 a 中排名为 k 的元素（0-indexed，即第 k+1 小）
// 执行完毕后，a[k] 处于其排序后应在的位置，其左侧 <= a[k]，右侧 >= a[k]
template <typename T>
T quick_select(std::vector<T> &a, int l, int r, int k) {
    static std::mt19937 rng{
        static_cast<std::mt19937::result_type>(
            std::chrono::steady_clock::now().time_since_epoch().count()
        )
    };

    while (l < r) {
        std::uniform_int_distribution<int> dist(l, r);
        std::swap(a[l], a[dist(rng)]);
        T pivot = a[l];

        int lt = l, gt = r, i = l + 1;
        while (i <= gt) {
            if (a[i] < pivot) std::swap(a[lt++], a[i++]);
            else if (a[i] > pivot) std::swap(a[i], a[gt--]);
            else ++i;
        }

        if (k < lt) {
            r = lt - 1;
        } else if (k > gt) {
            l = gt + 1;
        } else {
            return a[k]; // k 恰好落在 [lt, gt] 等于 pivot 的区间内
        }
    }
    return a[l];
}

4. 归并排序与分治思想 (Merge Sort)¶

归并排序将待排序区间从正中间二分，先递归将左半部分与右半部分分别排好序，再利用双指针线性合并两个有序序列。

4.1 归并求逆序对 (Counting Inversions)¶

在合并两个有序子序列 \(A[l \dots mid]\) 与 \(A[mid+1 \dots r]\) 时，若右半区当前指针所指元素 \(A[j] < A[i]\)（\(i \in [l, mid]\)），由于左半区已严格有序，则说明从 \(A[i]\) 到 \(A[mid]\) 的所有元素均严格大于 \(A[j]\)。

因此，当前元素 \(A[j]\) 与左半区剩余元素构成的逆序对数量恰为：

\[ \Delta = mid - i + 1 \]

#include <vector>

template <typename T>
long long merge_sort_inversions(std::vector<T> &a, std::vector<T> &tmp, int l, int r) {
    if (l >= r) return 0;
    int mid = l + (r - l) / 2;
    long long count = merge_sort_inversions(a, tmp, l, mid) +
                      merge_sort_inversions(a, tmp, mid + 1, r);

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            tmp[k++] = a[j++];
            count += (mid - i + 1); // 累加跨区间的逆序对贡献
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int p = l; p <= r; ++p) a[p] = tmp[p];

    return count;
}

template <typename T>
long long count_inversions(std::vector<T> a) {
    if (a.empty()) return 0;
    std::vector<T> tmp(a.size());
    return merge_sort_inversions(a, tmp, 0, static_cast<int>(a.size()) - 1);
}

4.2 链表自底向上迭代归并排序 (严格 \(\mathcal{O}(1)\) 空间)¶

单向链表无法高效随机访问，快排会因指针跳转缺乏局部性而变慢。归并排序是链表排序的最佳选择。采用自底向上（Bottom-Up）以步长 \(1, 2, 4, \dots, 2^k\) 迭代切分并合并子链表，可达到严格 \(\mathcal{O}(N \log N)\) 时间复杂度与 \(\mathcal{O}(1)\) 额外空间复杂度。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class ListSort {
private:
    // 从 head 出发截断出长度为 step 的前缀子链表，返回被切断的下一段链表头指针
    static ListNode* split(ListNode *head, int step) {
        if (!head) return nullptr;
        for (int i = 1; head->next && i < step; ++i) {
            head = head->next;
        }
        ListNode *second = head->next;
        head->next = nullptr;
        return second;
    }

    // 合并两个升序子链表，返回合并后的首尾指针
    static std::pair<ListNode*, ListNode*> merge(ListNode *l1, ListNode *l2) {
        ListNode dummy(0);
        ListNode *tail = &dummy;
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        tail->next = l1 ? l1 : l2;
        while (tail->next) tail = tail->next;
        return {dummy.next, tail};
    }

public:
    static ListNode* sort_list(ListNode *head) {
        if (!head || !head->next) return head;

        // 统计链表长度
        int length = 0;
        for (ListNode *curr = head; curr; curr = curr->next) ++length;

        ListNode dummy(0);
        dummy.next = head;

        for (int step = 1; step < length; step <<= 1) {
            ListNode *prev = &dummy;
            ListNode *curr = dummy.next;

            while (curr) {
                ListNode *left = curr;
                ListNode *right = split(left, step);
                curr = split(right, step);

                auto [merged_head, merged_tail] = merge(left, right);
                prev->next = merged_head;
                prev = merged_tail;
            }
        }
        return dummy.next;
    }
};

5. 原地堆排序 (Heap Sort)¶

堆排序利用完全二叉树的父子节点索引关系（\(0\)-indexed 下，节点 \(i\) 的左儿子为 \(2i+1\)，右儿子为 \(2i+2\)，父节点为 \(\lfloor (i-1)/2 \rfloor\)）。

5.1 线性建堆时间复杂度证明¶

从最后一个非叶子节点 \(\lfloor N/2 \rfloor - 1\) 开始逆序执行下沉（sift_down）：

高度为 \(h\)（以叶子高度为 \(0\)）的层最多有 \(\lceil N / 2^{h+1} \rceil\) 个节点；
每个节点最多下沉 \(h\) 次。

总比较与交换次数上限为：

\[ S = \sum_{h=1}^{\lfloor \log_2 N \rfloor} \frac{N}{2^{h+1}} \cdot h = \frac{N}{2} \sum_{h=1}^{\lfloor \log_2 N \rfloor} \frac{h}{2^h} \]

考虑级数 \(\sum_{h=1}^{\infty} \frac{h}{2^h} = 2\)，代入可得：

\[ S < \frac{N}{2} \cdot 2 = N = \mathcal{O}(N) \]

因此，原地自底向下建堆仅耗费严格 \(\mathcal{O}(N)\) 线性时间。

5.2 原地堆排序模板¶

#include <vector>
#include <algorithm>

template <typename T>
void sift_down(std::vector<T> &a, int n, int i) {
    while (true) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && a[left] > a[largest]) largest = left;
        if (right < n && a[right] > a[largest]) largest = right;

        if (largest == i) break;
        std::swap(a[i], a[largest]);
        i = largest;
    }
}

template <typename T>
void heap_sort(std::vector<T> &a) {
    int n = a.size();
    if (n <= 1) return;

    // 1. 线性 O(N) 原地构建大顶堆
    for (int i = n / 2 - 1; i >= 0; --i) {
        sift_down(a, n, i);
    }

    // 2. 原地抽取堆顶放入末尾
    for (int i = n - 1; i > 0; --i) {
        std::swap(a[0], a[i]); // 堆顶最大值移至数组有序区首部
        sift_down(a, i, 0);    // 缩减堆大小至 i，并重新下沉维护大顶堆
    }
}

6. 非比较类线性时间排序¶

6.1 计数排序 (Counting Sort)¶

适用于元素值域范围有限且非负的整数。先统计各元素出现频次，再计算频次数组的前缀和以确定每个数值在输出数组中的最终绝对位置，保证稳定性。

#include <vector>
#include <algorithm>

void counting_sort(std::vector<int> &a) {
    if (a.empty()) return;
    int min_v = *std::min_element(a.begin(), a.end());
    int max_v = *std::max_element(a.begin(), a.end());
    int k = max_v - min_v + 1;

    std::vector<int> count(k, 0);
    for (int x : a) count[x - min_v]++;

    // 前缀和转换
    for (int i = 1; i < k; ++i) count[i] += count[i - 1];

    std::vector<int> out(a.size());
    // 逆序回填确保稳定性
    for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {
        out[--count[a[i] - min_v]] = a[i];
    }
    a = std::move(out);
}

6.2 32 位整型极致常数基数排序 (Radix Sort - 4-Pass 256-Base LSD)¶

算法竞赛中面对 \(N \ge 10^6 \sim 10^7\) 的海量数据时，基于低位优先（LSD）将 32 位无符号整数按每 8 位（1 Byte，基数 \(R=256\)）拆分为 4 个轮次。每轮进行一次 \(\mathcal{O}(N + 256)\) 的计数排序。

此模板在常数上显著优于 std::sort，可将耗时压缩至后者的 \(1/3 \sim 1/4\)。

#include <vector>
#include <cstdint>
#include <algorithm>

void radix_sort_u32(std::vector<uint32_t> &a) {
    int n = a.size();
    if (n <= 1) return;

    std::vector<uint32_t> b(n);
    // 4 轮字节迭代，掩码 0xFF (255)
    for (int shift = 0; shift < 32; shift += 8) {
        int cnt[256] = {0};
        for (int i = 0; i < n; ++i) {
            cnt[(a[i] >> shift) & 0xFF]++;
        }
        for (int i = 1; i < 256; ++i) {
            cnt[i] += cnt[i - 1];
        }
        for (int i = n - 1; i >= 0; --i) {
            b[--cnt[(a[i] >> shift) & 0xFF]] = a[i];
        }
        a.swap(b);
    }
}

7. C++ 竞赛实战与严格弱序避坑指南¶

7.1 `std::sort` 内部架构 (Introsort)¶

C++ 标准库的 std::sort 结合了三种经典排序算法的精髓（又称内省排序 / Introsort）：

主干：随机/三数取中 Pivot 的快速排序；
防爆栈与防退化：当快排递归深度超过 \(2 \lfloor \log_2 N \rfloor\) 时，自动平滑退化至堆排序 (Heap Sort)，保证最坏情况不会劣于 \(\mathcal{O}(N \log N)\)；
小区间优化：当递归子区间长度小于某个阈值（通常为 16）时停止切分，最后对全局执行一次插入排序 (Insertion Sort)。

7.2 致命陷阱：严格弱序 (Strict Weak Ordering)¶

C++ 中传递给 std::sort 的比较器谓词 comp(a, b) 必须在数学上满足严格弱序（Strict Weak Ordering）的四条公理：

非自反性：comp(x, x) 恒为 false；
非对称性：若 comp(x, y) 为 true，则 comp(y, x) 必须为 false；
传递性：若 comp(x, y) 为 true 且 comp(y, z) 为 true，则 comp(x, z) 必须为 true；
不可比性的传递性：若 \(x\) 与 \(y\) 等价（即 !comp(x, y) && !comp(y, x)），且 \(y\) 与 \(z\) 等价，则 \(x\) 与 \(z\) 也必须等价。

[!CAUTION] 严禁在比较器中使用 <= 或 >=！若写成 return a.val <= b.val;，当数组中出现两个相同值 \(a = b\) 时，comp(a, b) 与 comp(b, a) 均返回 true，违反非自反性与非对称性。在 std::sort 内部执行快速排序的双向扫描 while (comp(*first, pivot)) 时，哨兵条件彻底失效，指针将无休止越界扫描，最终在判题机上导致 段错误 (Segmentation Fault / RE)。

// ❌ 错误示范：导致 Segmentation Fault
std::sort(a.begin(), a.end(), [](const Item &x, const Item &y) {
    return x.val <= y.val; // 致命错误！
});

// ✅ 正确示范：严格使用 < 比较，仅在非自反前提下分级比较
std::sort(a.begin(), a.end(), [](const Item &x, const Item &y) {
    if (x.val != y.val) return x.val < y.val;
    return x.id < y.id;
});

8. LeetCode 经典排序好题与模型精选¶

LeetCode 912 - 排序数组 (Sort an Array) 中等
提示

通用排序算法防退化大阅兵。
- 评测机包含已排序、逆序、几乎有序以及全相同元素（数万个相同的数值）的极端用例。
- 若手写快速排序，必须使用随机基准元配合三路划分（Three-Way Partitioning），否则在全等用例下递归深度退化为 \(\mathcal{O}(N)\) 导致超时 (TLE)；
- 也可直接使用堆排序或归并排序，严格以 \(\mathcal{O}(N \log N)\) 稳定通过。
LeetCode 215 - 数组中的第 K 个最大元素 (Kth Largest Element in an Array) 中等
提示

快速选择算法（Quickselect）的标杆题。
- 目标是寻找第 \(k\) 大元素，等价于寻找升序排序后下标为 \(n - k\) 的元素。
- 每次利用三路划分将序列切分为 \((< pivot)\)、\((== pivot)\)、\((> pivot)\)。
- 若目标下标 \(n - k\) 恰好落在中间相等区间内，直接返回 \(pivot\)；否则仅需单向递归左侧或右侧。
- 期望时间复杂度严格为 \(\mathcal{O}(N)\)，空间复杂度 \(\mathcal{O}(1)\)。竞赛中亦可直接调用 std::nth_element(nums.begin(), nums.begin() + n - k, nums.end())。
LeetCode 75 - 颜色分类 (Sort Colors) 中等
提示

荷兰国旗问题（三路划分的原型题）。
- 仅包含 \(0, 1, 2\) 三种数值，要求只遍历一次且仅使用常数空间的条件下拉齐。
- 维护三个指针：\(p_0\) 指向 \(0\) 的最右边界末尾，\(p_2\) 指向 \(2\) 的最左边界开头，\(curr\) 为当前扫描指针：
- 若 \(nums[curr] == 0\)，交换 \(nums[curr]\) 与 \(nums[p_0]\)，并将 \(p_0\) 与 \(curr\) 均向右移动一步；
- 若 \(nums[curr] == 2\)，交换 \(nums[curr]\) 与 \(nums[p_2]\)，此时仅将 \(p_2\) 向左移动一步（\(curr\) 不动，因为换过来的新元素尚未检查）；
- 若 \(nums[curr] == 1\)，直接 \(curr\) 右移。
LeetCode 148 - 排序链表 (Sort List) 中等
提示

链表自底向上归并排序的极致空间优化。
- 题目要求 \(\mathcal{O}(N \log N)\) 时间复杂度与 \(\mathcal{O}(1)\) 额外空间复杂度。
- 若采用自顶向下递归二分，函数调用栈深度为 \(\mathcal{O}(\log N)\)，不符合常数空间要求。
- 采用自底向上归并：初始分段长度 \(step = 1\)，每次循环将相邻两个长度为 \(step\) 的有序子链表进行归并；每轮归并完毕后 \(step \leftarrow step \times 2\)，直至 \(step \ge length\)。
LeetCode 493 - 翻转对 (Reverse Pairs) 困难
提示

归并排序求贡献模型。
- 寻找满足 \(i < j\) 且 \(nums[i] > 2 \cdot nums[j]\) 的下标对。
- 在归并排序合并 \([l, mid]\) 与 \([mid+1, r]\) 之前，两个子区间分别已经有序。
- 利用双指针在有序性下单调推进：对于左半区的每个元素 \(nums[i]\)，维护右半区的指针 \(j\)，只要 \(nums[i] > 2 \cdot nums[j]\)，指针 \(j\) 就持续右移。当前 \(i\) 对应的满足条件的右半区元素个数恰为 \(j - (mid + 1)\)。
- 统计完成后再执行常规的双指针合并排序。时间复杂度 \(\mathcal{O}(N \log N)\)。注意 \(2 \cdot nums[j]\) 会发生 32 位整型溢出，需转换为 long long 比较。
LeetCode 164 - 最大间距 (Maximum Gap) 中等
提示

基于抽屉原理（Pigeonhole Principle）的桶排序应用。
- 题目强制要求在 \(\mathcal{O}(N)\) 时间与空间复杂度内求解无序数组排序后的最大相邻差值。
- 设全数组最小值为 \(min\)，最大值为 \(max\)。若元素互不相同，则这 \(N\) 个数将整个区间划分为 \(N-1\) 个间隙，平均间隙大小为 \(gap = \lfloor \frac{max - min}{N - 1} \rfloor\)。
- 由抽屉原理知：最大相邻间隙一定不会出现在同一个桶内，必发生在某个非空桶的最大值与紧随其后的下一个非空桶的最小值之间。
- 因此建立 \(N-1\) 个桶，每个桶仅需维护落入该桶的局部最小值与最大值。最后顺序遍历所有非空桶，计算相邻桶跨度之差的最大值即可，时间严格 \(\mathcal{O}(N)\)。
LeetCode 56 - 合并区间 (Merge Intervals) 中等
提示

区间贪心与排序双指针基石。
- 将所有区间按左端点升序排序。
- 遍历区间序列：
- 若当前区间的左端点 \(\le\) 前一个区间的右端点，说明发生重叠，合并两区间并扩展当前合并右边界为 \(\max(end, curr.end)\)；
- 若当前区间的左端点 \(>\) 前一个区间的右端点，说明无交集，将前一个区间加入答案集合，并开启新区间维护。
LeetCode 179 - 最大数 (Largest Number) 中等
提示

自定义偏序关系与传递性数学证明。
- 将数字转为字符串形式，定义两个字符串 \(a\) 与 \(b\) 的比较规则为：若拼接字符串 \(a + b > b + a\)，则 \(a\) 应排在 \(b\) 之前。
- 严格弱序传递性证明：将字符串视为 \(B\) 进制整数（\(B=10\)），\(a + b\) 对应代数式 \(a \cdot 10^{|b|} + b\)。不等式 \(a + b > b + a\) 等价于 \(\frac{a}{10^{|a|} - 1} > \frac{b}{10^{|b|} - 1}\)。由于实数域的大小比较具有严格传递性，该字符串比较器具备严格弱序性，排序安全。
- 特判：排序后若首位元素为 "0"，直接返回 "0"。
LeetCode 324 - 摆动排序 II (Wiggle Sort II) 中等
提示

Quickselect 中位数 + 虚拟下标映射三路划分（原地重排）。
- 目标是重新排列数组使得 \(nums[0] < nums[1] > nums[2] < nums[3] \dots\)。
- 首先调用 quick_select 或 std::nth_element 在 \(\mathcal{O}(N)\) 时间内找到序列中位数 \(mid\)；
- 将奇数下标（\(1, 3, 5, \dots\)）分配给大于中位数的数，偶数下标（\(0, 2, 4, \dots\)）分配给小于中位数的数；
- 定义虚拟下标映射函数：\(idx(i) = (1 + 2i) \pmod{n \mid 1}\)，在虚拟坐标下运用荷兰国旗三路划分，实现严格 \(\mathcal{O}(N)\) 时间与 \(\mathcal{O}(1)\) 空间。
LeetCode 295 - 数据流的中位数 (Find Median from Data Stream) 困难
提示

动态维护序列有序性与对顶堆（Double Heap）设计。
- 在数据流动态插入的过程中实时输出中位数。
- 维护两个堆：大顶堆（维护较小的前一半数值）与小顶堆（维护较大的后一半数值）。
- 维持不变量：大顶堆元素个数等于小顶堆元素个数，或比小顶堆多 1。
- 每次插入新数值后，动态平衡两堆大小与堆顶元素单调性；查询中位数只需 \(\mathcal{O}(1)\) 读取堆顶。单次插入复杂度 \(\mathcal{O}(\log N)\)。

9. 排序的最少交换次数专题 (Minimum Swaps to Sort)¶

在算法竞赛与面试高频题中，“将序列排好序所需的最少交换次数”是一类极具数学美感的经典专题。根据允许交换的操作约束，主要分为两大核心理论模型：

允许交换任意两元素 \(\implies\) 置换环理论（Permutation Cycles）
仅允许交换相邻两元素 \(\implies\) 逆序对理论（Inversion Number）

9.1 模型一：允许交换任意两个元素（置换环理论）¶

数学原理与证明¶

设数组大小为 \(N\) 且元素各不相同。我们将每个元素当前下标 \(i\) 与其排序后应当所处的最终目标下标 \(target[i]\) 连一条有向边 \(i \to target[i]\)。由于每个位置有且仅有一个出度和一个入度，整个有向图必然被唯一分解为若干个互不相交的环（置换环，Disjoint Cycles）。

引理 1（环内交换分裂）：对同一个置换环内的任意两个元素进行一次交换，该环必然分裂为两个独立的子置换环。
引理 2（跨环交换合并）：对分别属于两个不同置换环的元素进行一次交换，这两个环必然合并为一个更大的置换环。
目标状态：完全排好序的数组包含 \(N\) 个长度为 1 的自环（每个元素各自构成一个自环，即 \(target[i] = i\)）。

设初始时整个数组分解出了 \(k\) 个置换环，各环长度分别为 \(L_1, L_2, \dots, L_k\)（满足 \(\sum_{i=1}^k L_i = N\)）。由于每次交换最多只能使图中的置换环总数增加 1，要把 \(k\) 个环变成 \(N\) 个自环，所需的最少交换次数严格为：

\[ \text{Min Swaps} = \sum_{i=1}^{k} (L_i - 1) = \sum_{i=1}^{k} L_i - \sum_{i=1}^{k} 1 = N - k \]

即：最少交换次数 = 元素总数 - 置换环总个数。

C++ 模板实现¶

#include <vector>
#include <algorithm>
#include <numeric>

// 计算将数组 a（假设无重复元素）排好序所需的最少任意两两交换次数
// 时间复杂度: O(N log N) (瓶颈在排序离散化)
// 空间复杂度: O(N)
int min_swaps_to_sort(std::vector<int> a) {
    int n = a.size();
    if (n <= 1) return 0;

    // 1. 离散化获取排序后的目标下标
    std::vector<int> target = a;
    std::sort(target.begin(), target.end());

    std::vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        p[i] = std::lower_bound(target.begin(), target.end(), a[i]) - target.begin();
    }

    // 2. 遍历求置换环个数
    std::vector<bool> visited(n, false);
    int cycles = 0;

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            ++cycles;
            int curr = i;
            while (!visited[curr]) {
                visited[curr] = true;
                curr = p[curr]; // 顺着置换边跳转
            }
        }
    }

    // 最少交换次数 = 元素个数 - 环个数
    return n - cycles;
}

9.2 模型二：仅允许交换相邻两个元素（逆序对理论）¶

数学原理与证明¶

在任意序列 \(A\) 中，若存在一对下标 \(i < j\) 满足 \(A[i] > A[j]\)，则称 \((A[i], A[j])\) 为一个逆序对（Inversion）。记序列中的逆序对总数为 \(\text{inv}(A)\)。

性质 1：交换任意两个相邻元素 \((A[i], A[i+1])\)，不会改变除这一对元素之外任何其他数对的相对先后顺序；
性质 2：若 \(A[i] > A[i+1]\)，相邻交换后该逆序对被消除，全序列逆序对总数恰好减少 1（\(\text{inv} \leftarrow \text{inv} - 1\)）；若 \(A[i] \le A[i+1]\)，交换后逆序对总数增加 1；
性质 3：完全升序排好序的序列其逆序对总数严格为 0。

由于一次相邻交换至多只能将逆序对总数减少 1，因此：

\[ \text{Min Adjacent Swaps} = \text{inv}(A) \]

仅通过相邻交换将数组排好序的最少操作次数，严格等于该数组的逆序对总数。可通过归并排序或树状数组在 \(\mathcal{O}(N \log N)\) 复杂度内求出。

9.3 衍生变种：特殊约束下的最少交换¶

只能与 0 交换（8 数码 / 滑块难题基石）：
规定每次操作只能将某个数字与空位（数字 0）交换；
若 0 所在的置换环长度为 \(L_0\)，0 已经在环内，只需 \(L_0 - 1\) 次交换即可解开该环；
若某个置换环不包含 0，长度为 \(L\)（\(L > 1\)），则必须先消耗 1 次交换将 0 换入该环中，再消耗 \(L\) 次将该环归位，总代价为 \(L + 1\) 次交换！
包含重复元素的最少交换：
当数组包含重复元素时，目标位置不唯一，最少两两交换等价于在包含重复字符的有向图中寻找最大环分解（Maximum Cycle Packing），属于 NP-Hard 变种，在小规模数据下通过状压 DP 或 A* 启发式搜索求解。

9.4 最少交换次数经典好题精选¶

LeetCode 2471 - 逐层排序二叉树所需的最少操作数目 (Minimum Number of Operations to Sort a Binary Tree by Level) 中等
提示

置换环裸题。
- 使用 BFS 逐层遍历二叉树，提取每一层的节点值数组。
- 每一层节点均可以任意两两交换，各层之间互不干扰。
- 对每一层的数组调用上述置换环模板，计算将该层排序所需的最少交换次数 \(N_{layer} - cycles\)，最后将所有层的交换次数累加即为答案。
LeetCode 765 - 情侣牵手 (Couples Holding Hands) 困难
提示

置换环与并查集连通块模型。
- 共有 \(N\) 对情侣（\(2N\) 个人），每张双人沙发应坐一对情侣。情侣 \(2i\) 和 \(2i+1\) 属于第 \(i\) 对。
- 将每对情侣看作图中的一个顶点（共 \(N\) 个顶点）。如果某张沙发上坐了属于情侣组 \(u\) 和情侣组 \(v\) 的两个人（\(u \ne v\)），说明这两对情侣被错误地牵扯在一起，在顶点 \(u\) 和 \(v\) 之间连一条无向边。
- 使用并查集维护所有顶点的连通分量：若一个连通分量包含 \(C\) 对情侣，则至少需要 \(C - 1\) 次交换才能使这 \(C\) 对情侣各自牵手。
- 全局最少交换次数 \(= N - \text{连通分量个数}\)。
LeetCode 1850 - 邻位交换的最小次数 (Minimum Adjacent Swaps to Reach the Kth Smallest Number) 中等
提示

next_permutation + 相邻交换贪心求逆序距离。
- 首先调用 \(k\) 次 std::next_permutation 得到原字符串变换后的第 \(k\) 个妙数目标串 \(T\)。
- 问题转化为：将初始字符串 \(S\) 仅通过相邻字符交换，变换为目标字符串 \(T\) 所需的最少步数。
- 贪心策略：从左往右遍历 \(S\) 的每一位 \(i\)，在 \(S[i \dots n-1]\) 中寻找第一个与 \(T[i]\) 相等的字符下标 \(j\)，然后通过相邻交换将其一步步“冒泡”前移至位置 \(i\)。
- 所需的相邻交换次数恰为 \(j - i\)。双指针模拟总复杂度 \(\mathcal{O}(N^2)\)，因为 \(N \le 1000\) 远小于上限，可秒级通过。
LeetCode 1505 - 最多 K 次交换相邻数位后得到的最小整数 (Minimum Possible Integer After at Most K Adjacent Swaps On Digits) 困难
提示

相邻交换预算约束下的贪心 + 树状数组动态位移。
- 预算为 \(K\) 次相邻交换。为了让整数最小，高位应尽可能贪心放置最小的数字（从 \(0\) 到 \(9\) 尝试）。
- 预处理开 10 个队列记录数字 \(0 \sim 9\) 在原串中的所有原始出现下标。
- 从左至右填入答案位的过程中，枚举当前可以移动到此位置的最小数字 \(d \in [0, 9]\)：
- 获取该数字当前最早可用的原始下标 \(pos\)；
- 由于之前已有若干元素被移到前方，该数字实际需要跨越的相邻步数为 \(pos - \text{bit.query}(pos)\)；
- 若步数 \(\le K\)，则贪心选取该数字：将其移到当前位置，从预算中扣除步数 \(K \leftarrow K - steps\)，在树状数组中标记 \(pos\) 位置已被移除（bit.add(pos, 1)），并将该数字从对应队列中弹出。
LeetCode 2193 - 得到回文串的最少操作次数 (Minimum Number of Moves to Make Palindrome) 困难
提示

贪心双指针 + 相邻交换。
- 每次只能交换相邻两个字符。
- 双指针维护左右边界 \(l = 0, r = n - 1\)：
- 固定左端字符 \(S[l]\)，从右向左寻找第一个满足 \(S[k] == S[l]\) 的位置 \(k\)；
- 若找到了且 \(k \ne l\)，将 \(S[k]\) 顺次相邻交换移动至 \(r\)，交换代价为 \(r - k\)，同时 \(l++, r--\)；
- 若 \(k == l\)，说明字符 \(S[l]\) 是唯一出现奇数次的孤立字符，它最终必须位于回文串的正中央。此时暂不移动它，只计算它移动到正中心的步数 \(n/2 - l\)，并继续处理 \(l++\)。
LeetCode 1703 - 得到连续 K 个 1 的最少相邻交换次数 (Minimum Adjacent Swaps for K Consecutive Ones) 困难
提示

中位数贪心（货仓选址）+ 坐标归一化逆序距离。
- 仅允许相邻交换。提取所有 1 的原始下标数组 \(P = [p_0, p_1, \dots, p_{m-1}]\)。
- 目标是选取 \(K\) 个连续的 1，将它们移动为连续区间。
- 坐标归一化技巧：令 \(q_i = p_i - i\)。则原来将 1 移动为紧密相邻的最小相邻交换步数，等价于将 \(q_i\) 移动到同一个目标点 \(x\) 的曼哈顿距离总和 \(\sum |q_i - x|\)！
- 由经典数学性质（货仓选址模型），最优的聚集中心 \(x\) 必然是这 \(K\) 个数的中位数。
- 使用长度为 \(K\) 的滑动窗口，结合前缀和在 \(\mathcal{O}(1)\) 内计算各窗口内所有点到中位数的距离总和，整体时间复杂度 \(\mathcal{O}(N)\)。
LeetCode 854 - 相似度为 K 的字符串 (K-Similar Strings) 困难
提示

有重复字符的最少两两交换（有向图最大环分解）。
- 允许任意交换两元素，但包含重复字符。
- 寻找从 \(s1\) 变为 \(s2\) 的最少两两交换次数。
- 等价性转化：对于所有 \(s1[i] \ne s2[i]\) 的位置，建立一条有向边 \(s1[i] \to s2[i]\)。最少交换次数等于总边数减去有向图能分解出的最多不相交有向环个数。
- 在数据规模较小（\(N \le 20\)）时，可采用带剪枝的 BFS 或 A* 启发式搜索：
- 每次优先寻找长度为 2 的互补环（即 \(s1[i] == s2[j]\) 且 \(s1[j] == s2[i]\)），一次交换直接消去两个错位；
- 其余情况分支拓展，记录访问状态判重。

常用排序算法与快速选择¶

1. 比较类排序的理论下界¶

决策树模型证明 (Decision Tree Lower Bound)¶

2. 常用排序算法全景对比¶

3. 快速排序与快速选择 (Quick Sort & Quickselect)¶

3.1 常见退化陷阱与防范¶

3.2 竞赛级双路快速排序模板 (Hoare Partition + 随机化)¶

3.3 三路快速排序模板 (Three-Way Quick Sort)¶

3.4 快速选择算法 (Quickselect / Introselect)¶

4. 归并排序与分治思想 (Merge Sort)¶

4.1 归并求逆序对 (Counting Inversions)¶

4.2 链表自底向上迭代归并排序 (严格 \(\mathcal{O}(1)\) 空间)¶

5. 原地堆排序 (Heap Sort)¶

5.1 线性建堆时间复杂度证明¶

5.2 原地堆排序模板¶

6. 非比较类线性时间排序¶

6.1 计数排序 (Counting Sort)¶

6.2 32 位整型极致常数基数排序 (Radix Sort - 4-Pass 256-Base LSD)¶

7. C++ 竞赛实战与严格弱序避坑指南¶

7.1 std::sort 内部架构 (Introsort)¶

7.2 致命陷阱：严格弱序 (Strict Weak Ordering)¶

8. LeetCode 经典排序好题与模型精选¶

9. 排序的最少交换次数专题 (Minimum Swaps to Sort)¶

9.1 模型一：允许交换任意两个元素（置换环理论）¶

数学原理与证明¶

C++ 模板实现¶

9.2 模型二：仅允许交换相邻两个元素（逆序对理论）¶

数学原理与证明¶

9.3 衍生变种：特殊约束下的最少交换¶

9.4 最少交换次数经典好题精选¶

7.1 `std::sort` 内部架构 (Introsort)¶