快速排序

基本思想

通过一趟排序将序列分割为两部分，其中一部分的数据比另外一部分的所有数据都要小，然后按照同样的规则对这两个序列进行同样的操作，知道最后被分割的序列有且只有一个。
在程序中，如何实现一部分的数据比另外一部分的数据都要小，这里需要定义一个基数来作为比较，比这个基数小的分为一部分，比这个基数大的分为另外一部分。

示例

** 对序列[6 1 2 7 9 3 4 5 10 8]进行第一趟分割 **

1. 在序列中找一个数作为基数，为了方便，一边选择最左边或最右边的数，我们这里选择最左边的6作为基数。
2. 我们假设有一个男同学站左边的1上面，女同学站在右边的8上面。

3. 然后女同学先往左边走（因为选择最左边的6作为基数，为了在最后一步去基数交换，所以必须先让女生走），如果走到比基数6小的位置则停下；然后男生往右边走，走到比基数6大的位置停下；然后交换位置下面的数据。（以下图片都来自于《啊哈！算法》）

   
   Paste_Image.png

4. 重复第三步一次

   
   Paste_Image.png

5. 重复第三步第二次

   
   Paste_Image.png
6. 第一趟后的结果 [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)