选择最后一个元素为基准时Hoare分区快速排序失效问题求助

问题现象 #

实现Hoare分区方案的快速排序时，若将基准值设为数组末尾元素（int pivot = A[high]），测试用例「5 4 3 2 1」无法正常完成排序；但选择low到high-1区间内的元素作为基准时，排序功能正常。

问题原因 #

Hoare分区的核心逻辑是通过双指针从两端向中间遍历，交换不符合基准值大小关系的元素，最终返回左分区的边界索引j，保证左分区（lo到j）的元素均≤基准值，右分区（j+1到hi）的元素均≥基准值。

当选择末尾元素作为基准时，会触发以下致命问题：

• 右指针j的循环逻辑是do j--; while (A[j] > pivot)，由于基准值pivot = A[high]，当j移动到high位置时，A[j] == pivot，不满足循环条件，j会停在high位置。
• 左指针i最终会遍历到high位置（比如测试用例「5 4 3 2 1」的基准是1，所有元素都≥1），此时i >= j（i=high，j=high），返回j=high。
• 递归调用时，quick_sort(A, low, pivot)的参数是low到high，满足low < high的条件，会无限重复调用分区函数，导致栈溢出或程序死循环，无法完成排序。

解决方案 #

要在Hoare分区中使用末尾元素作为基准，需先将基准元素从末尾位置移至区间内的其他位置（比如中间位置），避免右指针j始终停在末尾。推荐以下实现方式：

方式：交换基准元素到中间位置后执行原Hoare分区 #

在分区函数开头，将末尾的基准元素与区间中间元素交换，再按维基百科的原逻辑执行分区，既保留Hoare分区的高效性，又避免指针死锁问题：

int hoare_partition(int A[], int low, int high){
    // 将末尾元素与中间元素交换，避免基准在末尾导致的指针死锁
    int mid = (low + high) / 2;
    std::swap(A[mid], A[high]);
    int pivot = A[mid]; // 此时基准为原末尾元素，位于中间位置
    
    int i = low - 1;
    int j = high + 1;
    while (true){
        do i++; while (A[i] < pivot);
        do j--; while (A[j] > pivot);
        if (i >= j) return j; 
        std::swap(A[i], A[j]);
    }
}

修改后的完整代码 #

#include <iostream>
#include <algorithm>

int hoare_partition(int A[], int low, int high){
    int mid = (low + high) / 2;
    std::swap(A[mid], A[high]);
    int pivot = A[mid];
    
    int i = low - 1;
    int j = high + 1;
    while (true){
        do i++; while (A[i] < pivot);
        do j--; while (A[j] > pivot);
        if (i >= j) return j; 
        std::swap(A[i], A[j]);
    }
}

void quick_sort(int A[], int low, int high){
    if (low < high){
        int pivot_idx = hoare_partition(A, low, high);
        quick_sort(A, low, pivot_idx);
        quick_sort(A, pivot_idx + 1, high);
    }
}

int main(){
    int n; 
    std::cin >> n;
    int A[n]; 
    for (int i = 0; i < n; i++) {
        std::cin >> A[i];
    }
    quick_sort(A, 0, n-1);
    for (int i = 0; i < n; i++) {
        std::cout << A[i] << " ";
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者Poor Noob At Code