数据结构：快速排序与冒泡排序深度解析及性能评测

3.1.2 代码实现

// 获取基准值 -- Hoare 版本
int _QuickSort_Hoare(int* arr, int left, int right) {
    int key = left; // 默认为初始 left 索引
    left++;         // left 移动一位开始寻找
    
    while (left <= right) {
        // right: 从右往左找比 key 小的
        while (left <= right && arr[right] > arr[key]) {
            right--;
        }
        // left: 从左往右找比 key 大的
        while (left <= right && arr[left] < arr[key]) {
            left++;
        }
        // 交换
        if (left <= right) {
            Swap(&arr[right], &arr[left]);
        }
    }
    // 交换 key 与 right
    Swap(&arr[key], &arr[right]);
    return right;
}

代码分析：

1. 时间复杂度： 找 key 的过程虽然看似嵌套循环，但实质是协同遍历，复杂度为 O(N)。整体快速排序平均复杂度为 O(n log n)。
2. 边界细节： 内层循环条件为何用 > 而非 >=？若使用 >=，在特定数据下可能导致递归次数退化至 N，使复杂度退化为 O(N²)。
3. 返回值： 最终 right 的位置即为基准值的最终位置，因为其右侧元素已验证为 >= key。

3.2 挖坑法

思路： 将基准值暂存，左侧留'坑'。先从右向左找比基准小的填入坑中，原位置变新坑；再从左向右找比基准大的填入，重复直至 left == right，最后将基准值放入坑中。

3.2.1 图解分析

初始 hole 在左侧，key 保存基准值。right 找到小值填入 hole，hole 移至 right；left 找到大值填入 hole，hole 移至 left。当 left == right 时，即为基准值归位点。

3.2.2 代码实现

// 版本 2 -- 挖坑法
int _QuickSort_Pit(int* arr, int left, int right) {
    int hole = left;
    int key = arr[left];
    
    while (left < right) {
        // right 找比 key 小的
        while (left < right && arr[right] > key) {
            right--;
        }
        arr[hole] = arr[right];
        hole = right;
        
        // left 找比 key 大的
        while (left < right && arr[left] < key) {
            left++;
        }
        arr[hole] = arr[left];
        hole = left;
    }
    arr[hole] = key;
    return right;
}

3.3 Lomuto 前后指针法

思路： 创建前指针 prev 和后指针 cur。cur 向前扫描，遇到比基准小的，prev 前移并与 cur 交换，确保小的都在基准左边。

3.3.1 代码实现

// 基准值版本 3：Lomuto 前后指针
int _QuickSort_Lomuto(int* arr, int left, int right) {
    int prev = left, cur = prev + 1;
    int key = left;
    
    while (cur <= right) {
        // 注意条件的设置：短路特性保证 prev 前移仅在交换前判断
        if (arr[cur] < arr[key] && ++prev != cur) {
            Swap(&arr[cur], &arr[prev]);
        }
        cur++;
    }
    Swap(&arr[key], &arr[prev]);
    return prev;
}

关键点： 条件 ++prev != cur 既完成了 prev 的前移，又判断了是否发生了无效交换。利用 && 的短路特性，顺序不可颠倒。

四、非递归版快速排序（面试必会）

非递归实现需借助栈（Stack）来模拟递归调用过程。

算法思路：

1. 初始化： 创建栈，将初始区间 [left, right] 压入。
2. 主循环： 栈不为空时，弹出区间起点和终点。
3. 分区： 对当前区间执行分区操作，得到基准位置 keyi。
4. 压栈： 若左右子区间长度大于 1，分别压入栈中。
5. 终止： 栈为空时结束。

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);
        
        // 分区操作
        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;
        
        // 处理子区间
        if (keyi + 1 < end) {
            STPush(&st, end);
            STPush(&st, keyi + 1);
        }
        if (begin < keyi - 1) {
            STPush(&st, keyi - 1);
            STPush(&st, begin);
        }
    }
    STDestroy(&st);
}

分析： 边界检查 keyi + 1 < end 确保区间至少有两个元素，避免对单元素区间进行无意义的栈操作。

五、低效交换——冒泡排序

冒泡排序通过重复遍历数列，比较相邻元素并交换，直到没有需要交换的元素。

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; // 优化：若无交换则提前结束
    }
}

六、性能评估与对比

6.1 多维度对比

6.2 实测时效对比

以下测试展示了不同规模下的耗时差异（单位：毫秒）。

#include "Sort.h"
#include <time.h>
#include <stdlib.h>

void PrintArr(int* arr, int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

void TestOP() {
    srand(time(0));
    const int N = 100000;
    int* a1 = (int*)malloc(sizeof(int) * N);
    int* a7 = (int*)malloc(sizeof(int) * N);
    
    for (int i = 0; i < N; ++i) {
        a1[i] = rand();
        a7[i] = a1[i];
    }
    
    int begin1 = clock();
    QuickSort(a1, 0, N - 1);
    int end1 = clock();
    
    int begin2 = clock();
    BubbleSort(a7, N);
    int end2 = clock();
    
    printf("QuickSort: %d ms\n", end1 - begin1);
    printf("BubbleSort: %d ms\n", end2 - begin2);
    
    free(a1);
    free(a7);
}

总结

快速排序与冒泡排序展现了效率与简洁的鲜明对比。快速排序的多种分区方法和递归/非递归实现，通过与冒泡排序的多维对比，揭示了算法设计的核心权衡：在性能与复杂度、效率与可读性之间寻求最优解。掌握这些经典算法，不仅在于理解其实现原理，更在于培养根据场景选择合适工具的工程思维。