老了。。。就好像很久不玩魔方忘记了玩法一样。。。

快排都不会写了。

于是下面重温一下写一个：

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))

【转载请附】愿以此功德，回向 >>

原文链接：http://www.huangwenchao.com.cn/2015/03/python-%e5%86%99%e7%9a%84%e5%bf%ab%e6%8e%92%e4%b8%8e-kth.html【Python 写的快排与 kth】