快速排序又稱分區交換排序(partition-exchange sort)
平均時間復雜度為O(nlogn)

from random import shuffle

def quick_sort(lst, left, right):
    # 當只有一個元素的時候退出遞歸
    if left < right:
        p = partition(lst, left, right)
        # 左右分區分別遞歸
        quick_sort(lst, left, p)
        quick_sort(lst, p+1, right)

def partition(lst, left, right):
    pivot = lst[right-1]    # 以最后一個元素為分區點
    i = left - 1    # -1
    # 遍歷序列
    for j in range(left, right):    # range(0,10) [0..9]
        # 如果小于分區點，則與i+1交換
        if lst[j] < pivot:
            i += 1
            lst[i], lst[j] = lst[j], lst[i]
    # 將pivot放入分區點(i+1)，與前半部分的下一個元素交換
    if lst[right-1] < lst[i+1]:
        lst[i+1], lst[right-1] = lst[right-1], lst[i+1]
    # 返回分區點索引
    return i+1

source = list(range(10))
shuffle(source)
# print(source)

# source = [5, 7, 6, 2, 1, 3, 4, 9, 0, 8]

quick_sort(source, 0, len(source))
print(source)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

參考：
https://zh.wikipedia.org/wiki/快速排序
http://yshblog.com/blog/170
https://blog.csdn.net/dnxbjyj/article/details/70217804
https://blog.csdn.net/razor87/article/details/71155518