第k个数

题目描述：给定一个长度为n的数组，找出数组中第k大的数，其中$1\le k \le n $。

思路：

1、使用快速排序算法，根据k，判断要找的数位于左半区间还是右半区间

2、判断方法为计算左半区间的区间长度，若k小于等于左半区间长度，则要找的数位于左半区间，此时要找的值为左半区间第k大的值；若k大于右半区间长度，则要找的数位于右半区间，此时要找的值为右半区间第$k-len(左半区间长度)$大的值。

3、递归进行选择，当$l \ge r$时，中止，返回$a[l]$

代码如下：

n, k = map(int, input().split())
a = list(map(int, input().split()))

def quick_select(a, l, r, k):
    if l >= r:
        return a[l]
    x = a[l + r >> 1]
    i = l - 1
    j = r + 1
    while i < j:
        i += 1
        while a[i] < x:
            i += 1

        j -= 1
        while a[j] > x:
            j -= 1

        if i < j:
            a[i], a[j] = a[j], a[i]

    length = j - l + 1 # 左半区间的区间长度
    if k <= length:
        return quick_select(a, l, j, k)
    else:
        return quick_select(a, j+1, r, k-length)

res = quick_select(a, 0, n-1, k)
print(res)