参考：
1 def quick_sort(ary): 2 return qsort(ary, 0, len(ary)-1) 3 4 def qsort(ary, left, right): 5 if left >= right: 6 return 7 temp = ary[left] 8 lp = left 9 rp = right10 while lp < rp:11 while ary[rp] >= temp and lp < rp:12 rp -= 113 while ary[lp] <= temp and lp < rp:14 lp += 115 ary[lp], ary[rp] = ary[rp], ary[lp]16 ary[left], ary[lp] = ary[lp], ary[left]17 qsort(ary, left, lp-1)18 qsort(ary, rp+1, right)19 return ary20 21 22 if __name__ == '__main__':23 a = [1,5,4,8,7,2,3,9,4,5,7]24 print(quick_sort(a))
算法步骤：
- 从数列中挑出一个元素作为基准数。
- 分区过程，将比基准数大的放到右边，小于或等于它的数都放到左边。
- 再对左右区间递归执行第二步，直至各区间只有一个数。
代码解释：
while lp < rp: while ary[rp] >= temp and lp < rp: rp -= 1 while ary[lp] <= temp and lp < rp: lp += 1 ary[lp], ary[rp] = ary[rp], ary[lp]
ary[left], ary[lp] = ary[lp], ary[left]
举例：
5 4 7 1 9 2 4 8
在这里取 5 为基准数, 从右往左扫描，当遇到比5小的数就停下（遇到4停下）。从左向右扫描，当遇到比5大的数就停下（遇到7停下）。
然后交换这两个数，则原数组变为 5 4 4 1 9 2 7 8。此时 lp 指向4， rp 指向7。
再次从右往左扫描，当遇到比5小的数就停下（遇到2停下）。从左向右扫描，当遇到比5大的数就停下（遇到9停下）。
然后交换这两个数，则原数组变为 5 4 4 1 2 9 7 8.此时 lp 指向2， rp 指向9.
再次从右往左扫面，rp -1 == lp。此时lp rp相等。此while lp < rp 循环结束。
数组为 5 4 4 1 2 9 7 8
交换基准数和刚才 lp == rp 的位置的数。ary[left], ary[lp] = ary[lp], ary[left]
数组变为 2 4 4 1 5 9 7 8 。
再将数组分为 2 4 4 1 和 9 7 8 两个数组分别处理。
这里采用的分治和递归方法。基本条件为：if left >= right: return
代码解释：
if left >= right: return
举例：当截取的数组中只有两个元素 [8,6] 的时候，qsort(ary, 0, -1) 和 qsort(ary, 1,1),
所以当 left >= right 时候， 就不对数组元素进行修改，直接 return 返回即可。