快速排序

思路：

1，每次从数组中选择一个数，可以是左端点、右端点、中点或任意点都行

2，根据选择的点x，将数组划分为两个区间，其中左区间的值均小于等于x，右区间的值均大于等于x

3，递归排序左区间和右区间，当待排序区间的长度为1或0时返回

其中，步骤二有一个技巧，即用双指针算法，左指针指向待排序区间的左端点，右指针指向待排序区间的右端点，然后左指针往右走，直到找到第一个大于等于x的点，停。右指针往左走，直到找到第一个小于等于x的点，停。若左指针仍在右指针左侧，则交换两个点的值。代码如下

i, j = l-1, r+1 #l，r为待排序区间的左右端点
while i < j:
    i += 1 # 先让i+=1是为了每次都能让i指向下一个点，因为下面的while循环不一定执行，因此上面i初始为i=l-1
    while a[i] < x:
        i += 1

    j -= 1 # 同上
    while a[j] > x:
        j += 1

    if i < j: # 此处必须判断i指针是否在j指针左侧，避免将已排序好的值交换
        a[i], a[j] = a[j], a[i]    

通过上述办法，可以将待排序区间划分为两个区间，左区间的值均小于等于x，右区间的值均大于等于x，其中 j 为两区间的边界点，有了上述方法，便可以很简单的写出快速排序，代码如下：

def quick_sort(a, l, r):
    if l >= r:
        return 
    x = a[l + r >> 1]
    i, j = l-1, r+1 #l，r为待排序区间的左右端点
    while i < j:
        i += 1 # 先让i+=1是为了每次都能让i指向下一个点，因为下面的while循环不一定执行，因此上面i初始为i=l-1
        while a[i] < x:
            i += 1

        j -= 1 # 同上
        while a[j] > x:
            j += 1

        if i < j: # 此处必须判断i指针是否在j指针左侧，避免将已排序好的值交换
            a[i], a[j] = a[j], a[i]  

    quick_sort(a, l, j) # 递归排序左区间
    quick_sort(a, j+1m r) # 递归排序右区间