数据结构：快速排序进阶优化

• 使用指针 begin 和 end 记录初始范围；
• cur 用于遍历，left 和 right 动态收缩；
• 最终形成 [begin, left-1] (小于), [left, right] (等于), [right+1, end] (大于) 三个区域。

实现步骤：

1. 选择基准（结合三数取中或随机法）；
2. 初始化指针：cur = left + 1, begin = left, end = right；
3. 遍历划分：
   • 若 arr[cur] < key：交换至左侧，left++, cur++；
   • 若 arr[cur] == key：直接跳过，cur++；
   • 若 arr[cur] > key：交换至右侧，right--（注意 cur 不变，需重新检查）；
4. 递归处理左右两个非等值区间。

void QuickSortMore(int* arr, int left, int right) {
    if (left >= right) return;
    
    // 可选：此处可调用 threewaymid 或随机法选基准
    // int midi = threewaymid(arr, left, right); swap(&arr[midi], &arr[left]);
    
    int key = arr[left];
    int cur = left + 1;
    int begin = left;
    int end = right;
    
    while (cur <= right) {
        if (arr[cur] < key) {
            swap(&arr[left], &arr[cur]);
            left++; cur++;
        } else if (arr[cur] > key) {
            swap(&arr[right], &arr[cur]);
            right--;
        } else {
            cur++;
        }
    }
    
    // 递归处理小于和大于的部分，等于部分无需排序
    QuickSortMore(arr, begin, left - 1);
    QuickSortMore(arr, right + 1, end);
}

总结： 三路划分是对传统快排的针对性优化，在重复元素场景下优势明显，而在随机分布场景下性能与传统快排接近，是一种通用的改进方案。

三、自省排序 (IntroSort)

自省排序结合了快速排序、堆排序和插入排序的优点。它通过监控递归深度动态调整策略，既保留了快排的平均高效性，又避免了最坏情况下的性能退化。

核心思想：

1. 初始阶段： 使用快速排序，利用其 O(n log n) 的平均效率；
2. 深度监控： 当递归深度超过阈值（通常为 2 * logN）时，切换为堆排序，防止快排退化为 O(n²)；
3. 小数组优化： 当子数组规模小于阈值（如 16）时，切换为插入排序，减少递归开销。

这种机制确保了算法在各种数据场景下的稳定性。

代码实现：

#include "introsort.h"

void Swap(int* x, int* y) {
    int tmp = *x; *x = *y; *y = tmp;
}

// 向下调整建堆
void AdjustDown(int* a, int n, int parent) {
    int child = parent * 2 + 1;
    while (child < n) {
        if (child + 1 < n && a[child + 1] > a[child]) ++child;
        if (a[child] > a[parent]) {
            Swap(&a[child], &a[parent]);
            parent = child; child = parent * 2 + 1;
        } else break;
    }
}

// 堆排序
void HeapSort(int* a, int n) {
    for (int i = (n - 1 - 1) / 2; i >= 0; --i) AdjustDown(a, n, i);
    int end = n - 1;
    while (end > 0) {
        Swap(&a[end], &a[0]);
        AdjustDown(a, end, 0);
        --end;
    }
}

// 插入排序
void InsertSort(int* a, int n) {
    for (int i = 1; i < n; i++) {
        int end = i - 1, tmp = a[i];
        while (end >= 0 && tmp < a[end]) { a[end + 1] = a[end]; --end; }
        a[end + 1] = tmp;
    }
}

// 三值取中
int MedianOfThree(int* arr, int left, int right) {
    int mid = left + (right - left) / 2;
    if (arr[left] > arr[mid]) Swap(&arr[left], &arr[mid]);
    if (arr[left] > arr[right]) Swap(&arr[left], &arr[right]);
    if (arr[mid] > arr[right]) Swap(&arr[mid], &arr[right]);
    Swap(&arr[left], &arr[mid]);
    return arr[left];
}

// 自省排序主逻辑
void IntroSort(int* a, int left, int right, int depth, int defaultDepth) {
    if (left >= right) return;
    
    // 小数组使用插入排序
    if (right - left + 1 < 16) {
        InsertSort(a + left, right - left + 1);
        return;
    }
    
    // 深度超限切换堆排序
    if (depth > defaultDepth) {
        HeapSort(a + left, right - left + 1);
        return;
    }
    
    depth++;
    int prev = left, cur = prev + 1, keyi = left;
    
    // 随机选 key 或三值取中
    int randi = left + (rand() % (right - left + 1));
    Swap(&a[left], &a[randi]);
    
    while (cur <= right) {
        if (a[cur] < a[keyi] && ++prev != cur) Swap(&a[prev], &a[cur]);
        ++cur;
    }
    Swap(&a[prev], &a[keyi]);
    keyi = prev;
    
    IntroSort(a, begin, keyi - 1, depth, defaultDepth);
    IntroSort(a, keyi + 1, end, depth, defaultDepth);
}

void QuickSort(int* a, int left, int right) {
    int depth = 0, N = right - left + 1, logn = 0;
    for (int i = 1; i < N; i *= 2) logn++;
    IntroSort(a, left, right, depth, logn * 2);
}

在实际工程中，像 LeetCode 912 题这类对性能要求较高的排序任务，直接使用上述优化后的版本往往比基础实现更能通过严苛的测试用例。掌握这些进阶技巧，能让你的排序算法在面对真实数据时更加稳健。