QuickSelect算法（类QuickSort实现）返回None问题排查求助

首先，你的代码里最核心的问题是递归调用时没有返回结果，这直接导致了函数有时返回None。除此之外，我们还可以优化partition函数的设计，让它更高效且符合QuickSelect的常规实现。

问题分析 #

• 递归无返回值：在j > statistic_order和j < statistic_order的分支中，你调用了RSelect但没有用return返回它的结果。当这些分支执行完毕后，函数没有任何返回语句，Python会默认返回None。
• Partition函数效率低：你通过array.index(pivot)来查找pivot的位置，这会遍历整个数组，完全没必要——我们可以在partition过程中直接跟踪pivot的最终索引，返回这个索引而不是修改后的数组。
• 手动构建子数组冗余：你用循环append构建子数组，其实用Python的切片语法可以更简洁高效地完成。

修复后的代码 #

优化后的Partition函数 #

首先，修改partition函数，让它返回pivot的最终索引，避免不必要的数组遍历：

from random import shuffle

def partition(array, leftend, rightend):
    # 选第一个元素作为pivot（因为我们会先打乱数组）
    pivot = array[leftend]
    i = leftend  # i是pivot最终要放置的位置的指针

    # 遍历leftend+1到rightend-1的元素
    for j in range(leftend + 1, rightend):
        if array[j] < pivot:
            i += 1
            array[i], array[j] = array[j], array[i]
    
    # 将pivot放到正确的位置
    array[leftend], array[i] = array[i], array[leftend]
    return i  # 返回pivot的索引

修复后的RSelect函数 #

接下来修复递归返回的问题，并简化子数组的构建：

def RSelect(array, statistic_order):
    n = len(array)
    if n == 1:
        return array[0]
    
    # 打乱数组，保证随机pivot
    shuffle(array)
    # 调用partition，获取pivot的索引
    pivot_idx = partition(array, 0, n)

    if pivot_idx == statistic_order:
        return array[pivot_idx]
    elif pivot_idx > statistic_order:
        # 递归处理左子数组，统计顺序不变
        return RSelect(array[:pivot_idx], statistic_order)
    else:
        # 递归处理右子数组，统计顺序需要减去左半部分的长度（包括pivot）
        return RSelect(array[pivot_idx+1:], statistic_order - pivot_idx - 1)

代码说明 #

• 递归返回修复：在两个递归分支中都添加了return，确保将递归调用的结果传递回去。
• Partition优化：直接在partition过程中跟踪pivot的位置，返回索引，避免了array.index(pivot)的O(n)遍历。
• 切片简化：用array[:pivot_idx]和array[pivot_idx+1:]直接生成子数组，替代手动循环append，代码更简洁高效。
• 参数简化：原函数的n参数可以用len(array)代替，减少冗余参数。

测试示例 #

测试你给出的例子（注意：当前代码实现的是第i小元素查找，对应你描述的[4,3,5,7]找第2小元素返回4的需求）：

print(RSelect([4,3,5,7], 1))  # 输出4，符合预期

如果你需要查找第i大元素（从大到小排序后的第i个），只需要修改partition里的判断条件为array[j] > pivot即可，这样大于pivot的元素会被放到左边，pivot的索引对应的就是从大到小的顺序。

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