数据结构自学Day13 -- 快速排序--“前后指针法”

快速排序的 “前后指针法”（也称为“Hoare划分方案”或“双指针遍历法”）是一种实现 partition（划分） 的思路，它与“挖坑法”不同，利用两个指针分别扫描元素并交换，从而实现原地划分。

往期“快速排序算法回顾”：

快速排序--挖坑法
快速排序-- 分而治之

🧠 “前后指针”思想

“前后指针法”指的是：

用两个指针（cur 和 prev），一个扫描数组，一个标记小于 pivot 的“边界”，通过遍历和交换，把比 pivot 小的元素移到前面，比 pivot 大的放后面，最后把 pivot 放到中间。

🧩 思路详解

假设存在一个数组

• 数组为 arr[left..right]；

• 选择 arr[right] 为基准值（pivot）；

• prev 初始化为 left - 1，指向已处理的最后一个小于 pivot 的元素；

• cur 从 left 开始遍历到 right - 1，用于寻找比pivot小的元素。

🤔思维导图

代码实现

int PartSort3(int* arr,int left,int right){
    assert(arr);
    int mid_index = get_midindex(arr,left,right);
    Swap(&arr[mid_index],&arr[right]);
    int key = arr[right];
    int prev = left-1;
    for(int cur = left;cur<right;++cur){
        if(arr[cur]<key){
            prev++;
            Swap(&arr[cur],&arr[prev]);
        }
    }
    //可选while循环
    // while (cur< right){
    //     if(arr[cur]<key)
    //     {
    //         prev++;
    //         Swap(&arr[cur],&arr[prev]);
    //     }
    //     cur++;
    // }
    prev++;
    Swap(&arr[right],&arr[prev]);
    return prev;
}

快速排序算法总结：

1. 分而治之的排序思想（标准快排）

2. 挖坑法（Hoare分区法）

3. 前后指针法（Lomuto分区法）

它们本质上都基于快速排序的“分而治之”思想，但实现方式不同，影响效率与处理方式也有所区别。