基本思想
通过一趟排序将序列分割为两部分，其中一部分的数据比另外一部分的所有数据都要小，然后按照同样的规则对这两个序列进行同样的操作，知道最后被分割的序列有且只有一个。
在程序中，如何实现一部分的数据比另外一部分的数据都要小，这里需要定义一个基数来作为比较，比这个基数小的分为一部分，比这个基数大的分为另外一部分。
示例
** 对序列[6 1 2 7 9 3 4 5 10 8]进行第一趟分割 **
- 在序列中找一个数作为基数，为了方便，一边选择最左边或最右边的数，我们这里选择最左边的6作为基数。
- 我们假设有一个男同学站左边的1上面，女同学站在右边的8上面。
-
然后女同学先往左边走（因为选择最左边的6作为基数，为了在最后一步去基数交换，所以必须先让女生走），如果走到比基数6小的位置则停下；然后男生往右边走，走到比基数6大的位置停下；然后交换位置下面的数据。（以下图片都来自于《啊哈！算法》）
Paste_Image.png -
重复第三步一次
Paste_Image.png -
重复第三步第二次
Paste_Image.png - 第一趟后的结果 [3 1 2 5 4 6 9 7 10 8]，然后把基数6前面和后面的分割为两个序列进行同样的操作。最后可完成升序排序。
python实现算法
#!/usr/bin/python
# encoding: utf-8
# 快速排序
def quickSort(alist, left, right):
# 判断结束递归
if left >= right:
return 0
# base为基数
base, i, j = alist[left], left, right
while i < j:
# 因为基数是最左边的数，所以要先从右边往左找
while (alist[j] >= base and i < j):
j -= 1
while (alist[i] <= base and i < j):
i += 1
# 找到一个比基数大，一个比基数小后，交换
alist[i], alist[j] = alist[j], alist[i]
# 最后与基数交换
alist[left], alist[i] = alist[i], alist[left]
# 递归处理分割后的序列
quickSort(alist, left, i - 1)
quickSort(alist, i + 1, right)
elem = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
quickSort(elem, 0, len(elem) - 1)
print(elem) #[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
时间复杂度
最坏的情况为N的平方
平均时间复杂度O(nlogn)
