如何生成快速排序最佳用例数组？（C语言，取末尾元素为基准）

要让选末尾元素作为基准的快速排序达到最佳性能（时间复杂度O(nlogn)），核心是每次分区后，基准元素恰好落在当前区间的中间位置，使得左右子区间长度相等（或差1），递归深度最小。

构造思路 #

我们可以通过递归的方式，从有序数组出发，将当前区间的中位数放到末尾（作为下一次分区的基准），再分别递归构造左右子区间的最佳用例：

1. 对于目标区间，先确定该区间的中位数（对应有序数组的中间元素）。
2. 将中位数放到区间的末尾位置（快排会选这个元素作为基准，分区后它会回到中间位置）。
3. 递归构造左子区间（所有小于中位数的元素）和右子区间（所有大于中位数的元素），同样遵循“中位数放末尾”的规则。

C语言实现代码 #

#include <stdio.h>
#include <stdlib.h>

// 递归填充最佳数组的辅助函数
static void fill_optimal(int *dest, int d_start, int d_end, int *src, int s_start, int s_end) {
    if (d_start > d_end) {
        return;
    }
    if (d_start == d_end) {
        dest[d_start] = src[s_start];
        return;
    }
    // 计算源数组中当前区间的中位数位置
    int len = s_end - s_start + 1;
    int mid_src = s_start + (len - 1) / 2;
    // 将中位数放到目标区间的末尾（作为快排的基准）
    dest[d_end] = src[mid_src];
    // 递归填充左子区间（小于中位数的元素）
    int left_len = mid_src - s_start;
    fill_optimal(dest, d_start, d_start + left_len - 1, src, s_start, mid_src - 1);
    // 递归填充右子区间（大于中位数的元素）
    int right_len = s_end - mid_src;
    fill_optimal(dest, d_start + left_len, d_end - 1, src, mid_src + 1, s_end);
}

// 生成最佳用例数组，n为数组长度（512<=n<=16384）
int* build_quicksort_best_case(int n) {
    int *arr = malloc(n * sizeof(int));
    if (!arr) {
        perror("malloc failed");
        return NULL;
    }
    int *sorted = malloc(n * sizeof(int));
    if (!sorted) {
        perror("malloc failed");
        free(arr);
        return NULL;
    }
    // 生成有序数组作为基准
    for (int i = 0; i < n; i++) {
        sorted[i] = i + 1;
    }
    // 填充最佳数组
    fill_optimal(arr, 0, n - 1, sorted, 0, n - 1);
    free(sorted);
    return arr;
}

// 测试用例
int main() {
    int n = 5;
    int *arr = build_quicksort_best_case(n);
    if (!arr) return 1;
    printf("最佳用例数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    free(arr);
    return 0;
}

为什么你之前的方法耗时更长？ #

如果生成的数组反而让快排变慢，大概率是构造逻辑错误，导致每次分区的基准元素无法落在中间位置：

• 比如误生成了有序数组：选末尾元素为基准的快排处理有序数组时，每次分区只能将基准放到区间的最右端，递归深度达到O(n)，时间复杂度退化为O(n²)，远慢于平均情况。
• 或者构造的数组让基准元素偏向一端，导致子区间长度差距过大，递归深度增加，分区效率下降。

验证方法 #

你可以在快排中加入统计：每次分区后记录基准元素的位置，看是否等于当前区间的中间位置（(start + end)/2）。如果大部分情况下都满足，说明数组构造正确。

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