快速排序法

quick sort
wiki
https://zhuanlan.zhihu.com/p/21839027

原地排序
   def quick_sort(alist, first, last):
    if first >= last:
        return
    mid_value = alist[first]
    low = first
    high = last
    while low < high:
        while low < high and alist[high] >= mid_value:
            high= high - 1
        alist[low] = alist[high]
        while low < high and alist[low] < mid_value:
            low =low + 1
        alist[high] = alist[low]
    alist[low] = mid_value
    quick_sort(alist, first, low-1)
    quick_sort(alist, low+1, last)

numbers = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
quick_sort(numbers,0,len(numbers)-1)
#assert numbers == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(numbers)

===============
def quick_sort(alist, first, last):
    print("alist是{},first是{},last是{}".format(alist,first,last))
    if first >= last:
        return
    mid_value = alist[first]
    print("mid_value是{}".format(mid_value))
    low = first
    print("low是{}".format(low))
    high = last
    print("high是{}".format(high))
    while low < high:
        while low < high and alist[high] >= mid_value:
            high =high-1
            print("high是{}".format(high))
        alist[low] = alist[high]
        print("alist[low]是{}".format(alist[high]))
        while low < high and alist[low] < mid_value:
            low =low+1
            print("low是{}".format(low))
        alist[high] = alist[low]
        print("alist[higt]是{}".format(alist[high]))
    alist[low] = mid_value
    quick_sort(alist, first, low-1)
    print("quick_sort(alist, first, low-1)是{}".format(alist))
    quick_sort(alist, low+1, last)
    print("quick_sort(alist, low+1, last)是{}".format(alist))
numbers = [9, 8, 7, 6, 99, 4, 3, 2, 56, 0]
quick_sort(numbers,0,len(numbers)-1)
#assert numbers == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(numbers)



簡單版本




《Python cookbook 第二版》 from 知乎

def qsort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        return qsort([x for x in arr[1:] if x < pivot]) + \
               [pivot] + \
               qsort([x for x in arr[1:] if x >= pivot])

一行語法

qs = lambda xs : ( (len(xs) <= 1 and [xs]) or [ qs( [x for x in xs[1:] if x < xs[0]] ) + [xs[0]] + qs( [x for x in xs[1:] if x >= xs[0]] ) ] )[0]