1. 思路讲解

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。

  1. 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
  2. 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
  3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。

2. 代码

""" 参考自： 啊哈算法 """
def quickSort(arr, left, right):
    # 递归出口
    if left >= right:  # 拆分到无数字或者只有一个数字
        return

    pivot = arr[left]  # 基准
    i = left
    j = right
    while(i < j):  # 或者 i ！= j
        # 顺序很重要，每次都需要从右往左找
        while (arr[j] >= pivot and i < j):
            j = j - 1
        # 再从左往右找
        while (arr[i] <= pivot and i < j):
            i = i + 1
        # 交换位置
        if (i < j): # 当左右两个哨兵i和j没有相遇时
            t = arr[i]
            arr[i] = arr[j]
            arr[j] = t
    # 当i==j,相遇时，将基数归位 (两个哨兵相遇的地方与pivot交换) 下面两句等同于 arr[left], arr[i] = arr[i], arr[left]
    arr[left] = arr[i]
    arr[i] = pivot

    #递归处理
    quickSort(arr, left, i - 1)  # i==j是两哨兵相遇的点
    quickSort(arr, i + 1, right)
    return arr

if __name__ == '__main__':
    arr = [3,5,4,2,6,1,9,7,8,10]
    res = quickSort(arr, 0, len(arr) - 1)
    print(res)

参考：

1.维基百科.
2. 漫画图解快速排序.
3. （公众号“五分钟学算法”）这或许是东半球分析十大排序算法最好的一篇文章.
4. 《啊哈算法》