Python代码

def quicksort(q, l, r, k):
    # 此函数功能：在q[l:r+1]中找第k小的数
    # 退出递归条件：此函数中q的区间会不断缩小，最终剩下的那一个数就是第k小的数
    if l >= r:
        return q[l]
    # 1. 确定分界点
    x = q[(l + r) // 2]
    # 2. 调整区间
    # 比较优雅的方式：两个指针
    i, j = l - 1, r + 1
    while i < j:
        while True:
            i += 1
            if q[i] >= x:
                break
        while True:
            j -= 1
            if q[j] <= x:
                break
        if i < j: 
            # 这里的if语句可以过滤掉前面两个while出来时i>=j的情况（这种情况下q[i]和q[j]就不应该交换了）
            q[i], q[j] = q[j], q[i]
    # 3. 递归判断：
    sl = j - l + 1 # 左半边长度
    if sl >= k:
        # 此时sl大于等于k，问题转化为在左半边找第k小的数
        return quicksort(q, l, j, k)
    else:
        # 此时sl小于k，问题转化为在右半边找第k-sl小的数
        return quicksort(q, j + 1, r, k - sl)

if __name__ == "__main__":
    n, k = list(map(int, input().split()))
    q = list(map(int, input().split()))
    res = quicksort(q, 0, n - 1, k)
    print(res)