数据结构：快速排序分区逻辑与冒泡排序效率对比

分析：

1. 时间复杂度： 单次分区 O(N)，总复杂度 O(n log n)。虽然看似嵌套循环，但实质是协同遍历，属于"伪嵌套"。
2. 条件细节： 内层循环 while (left <= right && arr[right] > arr[key]) 必须用 > 而非 >=。若相等不移动，极端情况下会导致递归次数退化至 N，复杂度变为 O(N²)。
3. 返回值： 最终 right 的位置一定是基准值的位置，因为 right 右侧元素已验证为 >= key。

2. 挖坑法

思路： 将基准值暂存，左侧留"坑"。从右向左找比基准小的填入坑中，形成新坑；再从左向右找比基准大的填入，直至 left == right，最后将基准值放入坑中。

图解：

代码实现：

// 版本 2 -- "挖坑法"
int _QuickSort(int* arr, int left, int right) {
    int hole = left; // 初始将'坑'放在最左侧
    int key = arr[left]; // key 保存基准值
    
    while (left < right) {
        // 先 right 进行寻找比 key 小的数据
        while (left < right && arr[right] > key) {
            right--;
        }
        // 交换数据、位置 arr[hole]= arr[right]; right 成为新'坑'
        arr[hole] = arr[right];
        hole = right;
        
        // 再 left 找比 key 大的数据
        while (left < right && arr[left] < key) {
            left++;
        }
        // 交换数据、位置; left 成为新'坑'
        arr[hole] = arr[left];
        hole = left;
    }
    // 循环外 left == right，放入基准值
    arr[hole] = key;
    return right;
}

3. Lomuto 前后指针

思路： 创建前指针 prev 和后指针 cur。cur 向前寻找比基准值小的数据，找到后 prev++ 并与 cur 交换，使得小的都排在基准值左边。

图解：

代码实现：

// 基准值版本 3：lomuto 前后指针
int _QuickSort(int* arr, int left, int right) {
    int prev = left, cur = prev + 1;
    int key = left;
    
    while (cur <= right) {
        // cur 数据和基准值比较
        if (arr[cur] < arr[key] && ++prev != cur) {
            Swap(&arr[cur], &arr[prev]);
        }
        ++cur;
    }
    Swap(&arr[key], &arr[prev]);
    return prev;
}

注意： 条件 if (arr[cur] < arr[key] && ++prev != cur) 利用了短路特性。先判断大小，再执行 prev 前移并判断是否越界，避免无效交换。

高效交换：快速排序（非递归版）

面试中常考的非递归实现需借助栈来模拟递归调用。

思路：

1. 初始化栈，压入初始区间边界 [left, right]。
2. 当栈不为空时，弹出区间起点和终点。
3. 对区间进行分区，返回基准位置 keyi。
4. 若左右子区间长度大于 1，分别压入栈中。

代码实现：

// 非递归版本快速排序 ---- 栈
void QuickSortNorR(int* arr, int left, int right) {
    ST st;
    STInit(&st);
    STPush(&st, right);
    STPush(&st, left);
    
    while (!STEmpty(&st)) {
        // 取栈顶两次
        int begin = STTop(&st); STPop(&st);
        int end = STTop(&st); STPop(&st);
        
        // [begin,end]-----找基准值
        int keyi = begin;
        int prev = begin, cur = prev + 1;
        while (cur <= end) {
            if (arr[cur] < arr[keyi] && ++prev != cur) {
                Swap(&arr[prev], &arr[cur]);
            }
            ++cur;
        }
        Swap(&arr[prev], &arr[keyi]);
        keyi = prev;
        
        // 左序列 [begin,keyi-1]
        // 右序列 [keyi+1,end]
        if (keyi + 1 < end) {
            STPush(&st, end);
            STPush(&st, keyi + 1);
        }
        if (begin < keyi - 1) {
            STPush(&st, keyi - 1);
            STPush(&st, begin);
        }
    }
    STDesTroy(&st);
}

关键点： 压栈顺序是 (右，左)，弹出顺序是 (左，右)，保持对称性。边界检查确保只处理长度大于 1 的区间。

低效交换：冒泡排序

冒泡排序通过重复遍历数列，比较相邻元素并交换，直到没有需要交换的元素为止。虽然经典且易于理解，但效率较低。

void BubbleSort(int* arr, int n) {
    int exchange = 1;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                exchange = 0;
            }
        }
        if (exchange == 1) {
            break;
        }
    }
}

性能评估与总结

多维度对比

时效对比

在实际运行中，随着数据量增大，快速排序的优势会呈指数级放大。对于大规模数据，冒泡排序几乎不可用，而快速排序依然是工业界的首选之一。

结语：

快速排序与冒泡排序展现了效率与简洁的鲜明对比。掌握快速排序的三种分区方法和递归/非递归实现，有助于在工程实践中根据场景选择合适工具。算法学习的价值在于理解原理的同时，培养权衡性能与复杂度的思维。