老了。。。就好像很久不玩魔方忘记了玩法一样。。。
快排都不会写了。
于是下面重温一下写一个:
from random import shuffle
def qsort(ls, l=None, r=None):
if r is None: l, r = 0, len(ls)-1
if l < r:
m = partition(ls, l, r)
qsort(ls, l, m-1)
qsort(ls, m+1, r)
def kth(ls, k, l=None, r=None):
if r is None: l, r = 0, len(ls)-1
m = partition(ls, l, r)
return ls[m] if m == k else \
kth(ls, k, m+1, r) if m < k else \
kth(ls, k, l, m-1)
def partition(ls, l, r):
i = l - 1
j = l
while j < r:
if ls[j] < ls[r]:
ls[i+1], ls[j] = ls[j], ls[i+1]
i += 1
j += 1
ls[i+1], ls[r] = ls[r], ls[i+1]
return i+1
a = list(range(10))
shuffle(a)
qsort(a)
print(a)
shuffle(a)
print(kth(a, 3))