第 K 个最小的快速排序 python

Question

我必须得到未排序数组中第 K 个最小的元素。不是对整个数组进行排序，我只是尝试对包含第 K 个元素的子数组进行排序。然后我打印从 0 到 len(array)

的所有第 K 个

array = [6,5,4,3,2,1]
def quick_sort(lst, k):
    if len(lst) <= 1:
        return lst
    else:
        p = (lst[0] + lst[len(lst)-1])/2
        left = [x for x in lst if x <= p]
        right = [x for x in lst if x > p]
        
        if  k > len(left) -1 :
            k = k - len(left)+1
            return quick_sort(right,k)
        else:
            return quick_sort(left, k)
  
for i in range(len(array)):    
    print(*quick_sort(array,i+1))

我要得到1,2,3,4,5,6 但我的代码执行 2、3、5、6、6、6。我需要改变什么？

P.S。主要思想是不对所有数组进行排序并且不使用 python 排序函数

Answer 1

array = [6, 5, 4, 3, 2, 1]

def quick_sort(lst, k):
    if len(lst) <= 1:
        return lst
    else:
        p = (lst[0] + lst[-1]) / 2
        left = [x for x in lst if x <= p]
        right = [x for x in lst if x > p]

        if k > len(left):
            k = k - len(left)
            return quick_sort(right, k)
        else:
            return quick_sort(left, k)

for i in range(len(array)):
    print(*quick_sort(array, i + 1))

第 K 个最小的快速排序 python

K-th smallest quick sort python

python

arrays

sorting

quicksort