数据结构实战：快速排序分区逻辑与冒泡排序性能评测

三、找基准值 key 的三种递归版实战方法

3.1 快排核心构成：寻找 key 的算法之 "Hoare" 版本

算法思路： 创建左右'指针'，确定基准值；从右向左找出比基准值小的数据，从左向右找出比基准值大的数据，左右指针数据交换，进入下次循环。

3.1.1 画图理解算法

• 具体解析

前面提到要定义 left、right 来界定左右子序列，则初始在序列的最左边与最右边。对于 key 的选定，默认为初始的 left，那么 left 就需要 ++ 来到下一位，在 left++ 与 right 之间寻找合适基准值的位置。

接下来就是在整体的大循环中各自进行循环：left 找比 key 大的数，right 找比 key 小的数。因为是一小一大，那么循环条件就是 left <= right，不能越界重复寻找。当二者都处在各自的循环外就代表都找到了，那么就交换二者的数值，当然看图了解到交换条件是 left <= right。

最后 left > right，大循环结束，此时就要交换 key、right 完成基准值的寻找。

3.1.2 代码实战

// 获取基准值 -- hoare 版本
int _QuickSort(int* arr, int left, int right) {
    // 定义基准值
    int key = left;       // 默认为初始 left 值
    left++;               // 整体循环：left、right 遍历寻找
    
    while (left <= right) {
        // right: 从右往左找比 key 小的
        while (left <= right && arr[right] > arr[key]) {
            // 没找到，-- right;
            right--;
        }
        // 循环外：right 找到了
        
        // left: 从左往右找比 key 大的
        while (left <= right && arr[left] < arr[key]) {
            // 没找到，++ left;
            left++;
        }
        // 循环外：left 找到了
        
        // 二者都找到了，进行交换
        if (left <= right) {
            Swap(&arr[right], &arr[left]);
        }
    }
    // 交换 key、right
    Swap(&arr[key], &arr[right]);
    return right;
}

• 验证函数功能

// 快速排序 - 二叉树结构 // 主体框架
void QuickSort(int* arr, int left, int right) {
    if (left >= right) {
        return;
    }
    // 获取 key：单次
    int key = _QuickSort(arr, left, right);
    // 递归排序
    QuickSort(arr, left, key - 1);
    QuickSort(arr, key + 1, right);
}

void test01() {
    int arr[] = {5, 3, 9, 6, 2, 4, 7, 1, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("排序之前：");
    PrintArr(arr, n);
    QuickSort(arr, 0, n - 1);
    printf("排序之后：");
    PrintArr(arr, n);
}

int main() {
    test01();
    return 0;
}

3.1.3 代码分析

1. 找 key 算法的时间复杂度：O(N)。 虽然看着有循环的嵌套，但是经过作图发现循环始终是继承上回遍历的进度继续开始。也就是循环嵌套是"伪嵌套"，实质是协同完成一次遍历，而不是多次独立遍历。
2. 快速排序算法时间复杂度：O(n log n)。 递归的时间复杂度 = 单次递归时间复杂度（O(N)） * 递归次数（log n）。
3. 为什么最后的 right 的位置一定是基准值的位置？ 因为最后 right 的右边的元素已经验证为 >= key 的。

对于内层循环比如：while (left <= right && arr[right] > arr[key])，条件为什么不换成 >=？

根据一种最坏的情况演示，递归次数会从 log n 退化为 n，最终导致时间复杂度变大。

3.2 快排核心构成：寻找 key 的算法之'挖坑法'

算法思路： 创建左右'指针'，（left 不++）首先从右向左找出比基准小的数据，找到后立即放入坑中，当前位置变为新'坑'；然后从左到右找出比基准大的数据，找到后立即放到右边'坑'中，当前位置变为新'坑'；

结束循环后将最开始存储的分界值放入当前的坑中，返回当前'坑'的下标。

3.2.1 画图理解算法

• 具体解析

初始将 hole 放置在最左侧，同时 key 将元素保存空出'坑'。接着就是循环内的两个内层循环开始遍历，先是 right 从右向左找出比基准值小的数据 3 再放入 hole 中，并且 right 指向的位置变为'新坑'。同理，left 从左向右找比基准值大的数据 7 再放入 hole，并且 left 指向的位置变为'新坑'。

最终观察发现，当 left == right 时就是 key 要放入的'坑'的位置。

3.2.2 代码实战

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

• 验证函数功能

// 快速排序 - 二叉树结构 // 主体框架
void QuickSort(int* arr, int left, int right) {
    if (left >= right) {
        return;
    }
    // 获取 key：单次
    int key = _QuickSort(arr, left, right);
    // 递归排序
    QuickSort(arr, left, key - 1);
    QuickSort(arr, key + 1, right);
}

void test01() {
    int arr[] = {5, 3, 9, 6, 2, 4, 7, 1, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("排序之前：");
    PrintArr(arr, n);
    QuickSort(arr, 0, n - 1);
    printf("排序之后：");
    PrintArr(arr, n);
}

int main() {
    test01();
    return 0;
}

3.3 快排核心构成：寻找 key 的算法之'Lomuto 前后指针'

算法思路： 创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。

3.3.1 画图理解算法

• 具体解析

该方法与前面作算法题时用的'前后指针'的思想类似，让前指针 cur 向前寻找比基准值小的数据，找到后后指针 prev++ 与 cur 交换数据后，cur++。 重复进行以上过程，根据作图可知：循环终止条件为 cur > right 访问越界。

3.3.2 代码实战

// 基准值版本 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;
}

• 验证函数功能

// 快速排序 - 二叉树结构 // 主体框架
void QuickSort(int* arr, int left, int right) {
    if (left >= right) {
        return;
    }
    // 获取 key：单次
    int key = _QuickSort(arr, left, right);
    // 递归排序
    QuickSort(arr, left, key - 1);
    QuickSort(arr, key + 1, right);
}

void test01() {
    int arr[] = {5, 3, 9, 6, 2, 4, 7, 1, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("排序之前：");
    PrintArr(arr, n);
    QuickSort(arr, 0, n - 1);
    printf("排序之后：");
    PrintArr(arr, n);
}

3.3.3 代码分析

1. 对于条件语句 if (arr[cur] < arr[key] && ++prev != cur) 的设置问题！ 这个条件设置的很巧妙~，首先看后面的 ++prev != cur，该表达式实质上完成了两个任务：一个是 prev 的前移，另一个是判断是否相等。另外前后顺序的设置，因为是 && 有'短路'特性。所以如果顺序颠倒导致 prev 前移，但是没有交换，导致错误。
2. 定义了'前后指针'，为什么不直接传'指针'位置？ 为什么传 left、right，因为循环条件需要判断是否访问越界用到了 right。

四、高效交换——快速排序：非递归版（面试必会）

非递归版本的快速排序需要借助数据结构：栈。

算法思路： 初始化阶段： 创建一个栈并初始化，将初始排序区间的边界 [left, right] 压入栈中。（要注意：先压入右边界，再压入左边界（后进先）） 主循环阶段（循环条件：栈不为空时继续执行） 每次循环的操作：弹出区间：从栈中弹出两个元素：begin（区间起点）和 end（区间终点）弹出顺序与压入顺序相反；分区操作：调用 _QuickSort3 函数（或者重新定义）对 [begin, end] 区间进行分区，返回基准元素的位置 keyi；处理子区间：右子区间：如果 [keyi+1, end] 长度大于 1，压入栈中；左子区间：如果 [begin, keyi-1] 长度大于 1，压入栈中。 终止条件： 当栈为空时，说明所有需要排序的子区间都已处理完毕，销毁栈。

4.1 画图理解算法

4.2 代码实战

// 非递归版本快速排序 ---- 栈
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 end
        // 左序列 [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);
}

4.2.1 代码分析

1. 边界条件检查：避免不必要的栈操作 keyi + 1 < end 确保右区间至少有两个元素；begin < keyi - 1 确保左区间至少有两个元素。 （当区间只有一个元素或没有元素时（keyi+1 >= end 或 begin >= keyi-1），该区间已经有序。）
2. 压栈顺序是 (右，左)，弹出顺序是 (左，右)，这种操作的对称性要保证。

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

冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个相邻元素，如果它们的顺序错误就把它们交换过来。遍历会重复进行，直到没有需要交换的元素，这时数列排序完成。 对于冒泡排序，这个经典的教学产物都不陌生，这里就不过多介绍。

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"

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

void test1() {
    int a[] = {5, 3, 9, 6, 2, 4, 7, 1, 8};
    int size = sizeof(a) / sizeof(a[0]);
    printf("排序前:");
    PrintArr(a, size);
    // 直接插入排序
    // InsertSort(a, size);
    // 希尔排序
    // ShellSort(a, size);
    // 直接选择排序
    // SelectSort(a, size);
    // 堆排序
    // HeapSort(a, size);
    // 冒泡排序
    // BubbleSort(a, size);
    // 快速排序
    // QuickSort(a, 0, size - 1);
    // 非递归快速排序
    QuickSortNoare(a, 0, size - 1);
    printf("排序后:");
    PrintArr(a, size);
}

// 测试排序的性能对比
void TestOP() {
    srand(time(0));
    const int N = 100000;
    int* a1 = (int*)malloc(sizeof(int)* N);
    int* a2 = (int*)malloc(sizeof(int)* N);
    int* a3 = (int*)malloc(sizeof(int)* N);
    int* a4 = (int*)malloc(sizeof(int)* N);
    int* a5 = (int*)malloc(sizeof(int)* N);
    int* a6 = (int*)malloc(sizeof(int)* N);
    int* a7 = (int*)malloc(sizeof(int)* N);
    
    for (int i = 0; i < N; ++i) {
        a1[i] = rand();
        a2[i] = a1[i];
        a3[i] = a1[i];
        a4[i] = a1[i];
        a5[i] = a1[i];
        a6[i] = a1[i];
        a7[i] = a1[i];
    }
    
    int begin1 = clock();
    InsertSort(a1, N);
    int end1 = clock();
    
    int begin2 = clock();
    ShellSort(a2, N);
    int end2 = clock();
    
    int begin3 = clock();
    SelectSort(a3, N);
    int end3 = clock();
    
    int begin4 = clock();
    HeapSort(a4, N);
    int end4 = clock();
    
    int begin5 = clock();
    QuickSort(a5, 0, N - 1);
    int end5 = clock();
    
    int begin6 = clock();
    // MergeSort(a6, N);
    int end6 = clock();
    
    int begin7 = clock();
    BubbleSort(a7, N);
    int end7 = clock();
    
    printf("InsertSort:%d\n", end1 - begin1);
    printf("ShellSort:%d\n", end2 - begin2);
    printf("SelectSort:%d\n", end3 - begin3);
    printf("HeapSort:%d\n", end4 - begin4);
    printf("QuickSort:%d\n", end5 - begin5);
    // printf("MergeSort:%d\n", end6 - begin6);
    printf("BubbleSort:%d\n", end7 - begin7);
    
    free(a1);
    free(a2);
    free(a3);
    free(a4);
    free(a5);
    // free(a6);
    free(a7);
}

int main() {
    TestOP();
    // test1();
    return 0;
}

总结

快速排序与冒泡排序展现了效率与简洁的鲜明对比。快速排序的三种分区方法和递归/非递归实现，通过与冒泡排序的多维对比，揭示了算法设计的核心权衡：在性能与复杂度、效率与可读性之间寻求最优解。

掌握这些经典算法，不仅在于理解其实现原理，更在于培养根据场景选择合适工具的工程思维。这正是算法学习的真正价值——在理论深度与实践需求间建立智慧桥梁。