快速排序

快速排序之所以比较快，是因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候
设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全
部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进
行交换，交换的距离就大得多了。因此总的比较和交换次数就少了，速度自然就提高了。

def quick_sort(a, left, right):
    if left >= right:
        return
    # temp保存基准数
    temp = a[left]
    i = left
    j = right
    while i!=j:
        # 必须从j开始，以便于基准数归为
        while a[j] >= temp and j>i:
            j -= 1
        while a[i] <= temp and j>i:
            i += 1
        if j > i:
            a[i], a[j] = a[j], a[i]
    # 基准数归位
    a[left], a[i] = a[i], temp
    quick_sort(a, left, i-1)
    quick_sort(a, i+1, right)

if __name__ == '__main__':
    a = []
    n = int(raw_input())
    for i in range(n):
        a.append(int(raw_input()))
    quick_sort(a, 0 , n-1)

最差时间复杂度为O(N^2)，平均时间复杂度为O(NlogN)