如何不通过排序递归查找未排序数组的第n小值，现有实现出错求优化

现有代码问题分析 #

• 核心逻辑错误：直接对半拆分数组后分别求左右子数组对应位次的最小值再取最大值的逻辑完全不成立。拆分后没有做跨子数组的大小比较，右子数组中小于左子数组部分元素的值会被完全忽略，自然会出现漏值、结果错误的问题。比如示例中找第3小值时，按你的逻辑算出来的结果是5，和预期的7完全不符。
• 边界处理缺失：未处理index超出数组长度、index为0等非法输入场景，也没有兼容数组长度为奇数时的拆分适配。

正确实现方案：递归版快速选择 #

这是无需全排序找第k小值的标准算法，平均时间复杂度O(n)，符合你的递归要求。核心逻辑是选取基准值把数组划分为小于基准、等于基准、大于基准三个区间，根据目标位次所在区间直接返回结果或递归对应区间即可。

完整可运行代码 #

#include <stdio.h>

// 交换两个元素
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数，返回基准值最终所在的索引
int partition(int arr[], int left, int right) {
    int pivot = arr[right]; // 可选随机基准优化最坏情况性能
    int i = left;
    for (int j = left; j < right; j++) {
        if (arr[j] < pivot) {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[right]);
    return i;
}

// 递归查找第k小值，k从1开始计数适配你的需求
int findKthSmallest(int arr[], int left, int right, int k) {
    if (left == right) {
        return arr[left];
    }
    
    int pivotIndex = partition(arr, left, right);
    int rank = pivotIndex - left + 1; // 基准值在当前区间的位次
    
    if (k == rank) {
        return arr[pivotIndex];
    } else if (k < rank) {
        // 目标值在左区间，递归左半部分
        return findKthSmallest(arr, left, pivotIndex - 1, k);
    } else {
        // 目标值在右区间，递归右半部分，位次减去左区间总元素数
        return findKthSmallest(arr, pivotIndex + 1, right, k - rank);
    }
}

// 适配你原函数的输入接口
int func(int arr[], int size, int index) {
    if (index < 1 || index > size) {
        return -1; // 非法输入可自定义返回值
    }
    return findKthSmallest(arr, 0, size - 1, index);
}

// 测试用例
int main() {
    int array[] = {5,2,10,11,18,3,7,9,15,17};
    int size = sizeof(array)/sizeof(array[0]);
    printf("index=3 结果：%d\n", func(array, size, 3)); // 输出7
    printf("index=7 结果：%d\n", func(array, size, 7)); // 输出15
    return 0;
}

补充说明 #

• 该实现仅做分区操作，没有对数组全排序，符合你的要求。
• 如果需要避免最坏情况O(n²)的时间复杂度，可以把分区函数的基准值改为随机选取区间内的元素，平均性能会更稳定。
• 如果要求不能修改原数组，可以在递归时拷贝对应区间的元素到新数组再处理，仅会额外占用O(n)的空间。

内容的提问来源于stack exchange，提问作者יונתן אליהו