Synopsis: 快速排序通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

代码已上传到 https://github.com/wangy8961/python3-algorithms ，欢迎star

1. 算法介绍

快速排序（Quick Sort）又称分区交换排序（partition-exchange sort），简称快排。于1961年由Tony Hoare首次发表，它是一种比较排序，是不稳定的排序算法，这意味着不会保留相等排序项的相对顺序

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）：

首先从原始序列中，挑选一个基准（pivot）元素，可以选择第1个元素、最后1个元素或中间元素
将小于基准值的元素放在基准的左边，将大于基准值的元素放在基准的右边，基准处于数列的中间位置，称为一趟分区（partition）操作。相当于将基准元素放置到它应该在的位置上，左边序列全比它小，右边序列全比它大，暂时不用管左右序列是否有序排列
对小于基准值的子序列和大于基准值的子序列重复进行步骤1和步骤2，直到子序列只有1个元素时（肯定是有序的啦）

2. Python实现

2.1 算法1

假设序列的第1个元素为基准(pivot)，使用列表生成式(List Comprehensions)来查找比基准值小或大的元素序列：

def quick_sort(L):
    '''使用 '列表生成式(List Comprehensions)' 查找比 '基准(pivot)' 小或大的元素序列'''
    n = len(L)
    if n <= 1:
        return L

    pivot_value = L[0]
    lesser = [item for item in L[1:] if item <= pivot_value]
    greater = [item for item in L[1:] if item > pivot_value]

    return quick_sort(lesser) + [pivot_value] + quick_sort(greater)


if __name__ == '__main__':
    L1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print('Before: ', L1)
    sorted = quick_sort(L1)
    print('After: ', sorted)

# Output:
Before:  [54, 26, 93, 17, 77, 31, 44, 55, 20]
After:  [17, 20, 26, 31, 44, 54, 55, 77, 93]

也可以将上述排序函数改写为一行：

quick_sort = lambda L: L if len(L) <= 1 else quick_sort([i for i in L[1:] if i <= L[0]]) + [L[0]] + quick_sort([j for j in L[1:] if j > L[0]])

测试通过：

quick_sort = lambda L: L if len(L) <= 1 else quick_sort([i for i in L[1:] if i <= L[0]]) + [L[0]] + quick_sort([j for j in L[1:] if j > L[0]])

if __name__ == '__main__':
    L1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print('Before: ', L1)
    sorted = quick_sort(L1)
    print('After: ', sorted)

# Output:
Before:  [54, 26, 93, 17, 77, 31, 44, 55, 20]
After:  [17, 20, 26, 31, 44, 54, 55, 77, 93]

压力测试：

from timeit import timeit

def test():
    # import random
    # gen = (random.randint(1, 100) for i in range(100))  # 产生100个 1-99 范围内的随机整数
    # L = list(gen)
    L = [96, 2, 65, 23, 47, 58, 8, 48, 69, 92, 34, 83, 93, 47, 45, 55, 95, 15, 92, 24, 64, 19, 29, 55, 35, 48, 39, 29, 63, 94, 99, 38, 50, 10, 10, 93, 74, 27, 74, 44, 29, 81, 85, 86, 74, 30, 50, 50, 12, 12, 38, 75, 41, 87, 80, 97, 16, 48, 65, 69, 83, 71, 28, 9, 64, 69, 27, 74, 74, 86, 40, 69, 79, 79, 77, 100, 53, 72, 77, 16, 8, 36, 41, 58, 59, 29, 46, 79, 81, 66, 8, 35, 60, 52, 2, 82, 2, 36, 79, 66]
    quick_sort(L)

def quick_sort(L):
    n = len(L)
    if n <= 1:
        return L

    pivot_value = L[0]
    lesser = [item for item in L[1:] if item <= pivot_value]
    greater = [item for item in L[1:] if item > pivot_value]

    return quick_sort(lesser) + [pivot_value] + quick_sort(greater)


print('Quick sort function run 1000 times, cost: ', timeit('test()', 'from __main__ import test', number=1000), 'seconds.')

# Output:
Quick sort function run 1000 times, cost:  0.2375717348850251 seconds.

2.2 算法2

def quick_sort(L, first, last):
    '''使用 '递归(recursive)' 的方式，实现快速排序算法
    first 和 last 都表示序列的下标
    '''
    if first < last:  # 左、右子序列只剩一个元素时，退出递归 (first == last)
        pivot_index = partition(L, first, last)  # 返回 '基准' 值的最终正确位置的下标
        quick_sort(L, first, pivot_index-1)
        quick_sort(L, pivot_index+1, last)


def partition(L, first, last):
    '''一次快速排序的分区过程，将选定的 '基准(pivot)' 放到正确的位置上，小于它的值都在它的左边，大于它的值都在它的右边
    first 和 last 都表示序列的下标
    '''
    pivot_value = L[first]  # 可以选择序列的第1个元素、中间元素或最后1个元素为 '基准' 值，这里选择第1个

    leftmark = first + 1  # leftmark 游标从左向右查找比 '基准' 值大的元素
    rightmark = last  # rightmark 游标从右向左查找比 '基准' 值小的元素

    done = False
    while not done:
        # 当 leftmark 找到比 '基准' 值大的元素后，停下来
        while leftmark <= rightmark and L[leftmark] <= pivot_value:
            leftmark = leftmark + 1