算法1 quick-sort

时间复杂度

O(nlogn) - same as quick sort itself.

python 代码

N, k = [int(_) for _ in input().split()]
seq = [int(_) for _ in input().split()]
# print(N, k, seq)

def quick_sort(in_list, left, right):
    if left >= right:
        return

    pivot = in_list[(left+right)//2]
    a, b = left-1, right+1

    while a < b:
        while True:
            a += 1
            if in_list[a] >= pivot: break
        while True:
            b -= 1
            if in_list[b] <= pivot: break
        if a < b:
            in_list[a], in_list[b] = in_list[b], in_list[a]
    quick_sort(in_list, left, b)
    quick_sort(in_list, b+1, right)


quick_sort(seq, 0, N-1)
print(seq[k-1])  # position start from 0