基于Hoare划分的C语言快速排序降序排序异常问题

问题根源分析 #

你的代码存在两处核心问题，导致降序排序结果不符合预期：

1. 越界风险与循环条件缺失：第二个do-while循环未加入i < j的判断，当数组中所有元素都大于基准值时，i会持续递增直至超出数组范围，引发非法内存访问，导致排序逻辑异常。
2. 划分返回值与递归范围不匹配：Hoare划分的返回值与后续递归调用的范围不对应，原代码返回j+1并递归[inf, pivot-1]和[pivot+1, sup]，会跳过部分元素，导致排序不完整。

修复后的完整代码 #

#include <stdio.h>

void swap(int *x, int *y) {
    int tmp;

    tmp = *x;
    *x = *y;
    *y = tmp;
}

int partition (int *arr, int min, int max) {
    int x = arr[min];
    int i = min - 1;
    int j = max + 1;

    while (1) {
        // 从右往左找第一个 >= 基准值的元素（满足降序要求）
        do {
            j--;
        } while (i < j && arr[j] < x);
        // 从左往右找第一个 <= 基准值的元素，加入i<j防止越界
        do {
            i++;
        } while (i < j && arr[i] > x);
        if  (i < j)
            swap(&arr[i], &arr[j]);
        else
            return j; // 返回左半部分的最后一个索引
    }
}

void quickSort(int *arr, int inf, int sup) {
    if (arr) {
        if (inf < sup) {
            int pivot = partition(arr, inf, sup);
            quickSort(arr, inf, pivot); // 递归左半部分：[inf, pivot]
            quickSort(arr, pivot + 1, sup); // 递归右半部分：[pivot+1, sup]
        }
    }
}

int main() {
    int array[] = { 151, 153, 134, 137, -1, -1, -1, -1, -1, 158, 158, -1, -1, 133, 127, 158, 158 };

    int dim = sizeof(array) / sizeof(int);
    quickSort(array, 0, dim - 1);

    for (int i = 0; i < dim; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

修复说明 #

1. 补充循环边界判断：在第二个do-while中加入i < j，确保i不会超出有效索引范围，避免非法内存访问。
2. 修正划分返回值：Hoare划分完成后，j是左半部分（所有元素≥基准值）的最后一个索引，返回j而非j+1，保证递归范围的正确性。
3. 调整递归范围：左半部分递归范围为[inf, pivot]，右半部分为[pivot+1, sup]，确保所有元素都被纳入排序流程，不会出现遗漏。

运行修复后的代码，输入给定数组将得到预期的降序结果：

158 158 158 158 153 151 137 134 133 127 -1 -1 -1 -1 -1 -1 -1

内容的提问来源于stack exchange，提问作者buben