def quick_sort(alist, start, end):
    """快速排序"""

    # 遞歸的退出條件
    if start >= end:
        return

    # 設定起始元素為要尋找位置的基準元素
    mid = alist[start]

    # low為序列左邊的由左向右移動的游標
    low = start

    # high為序列右邊的由右向左移動的游標
    high = end

    while low < high:
        # 如果low與high未重合，high指向的元素不比基準元素小，則high向左移動
        while low < high and alist[high] >= mid:
            high -= 1
        # 將high指向的元素放到low的位置上
        alist[low] = alist[high]

        # 如果low與high未重合，low指向的元素比基準元素小，則low向右移動
        while low < high and alist[low] < mid:
            low += 1
        # 將low指向的元素放到high的位置上
        alist[high] = alist[low]

    # 退出循環(huán)后，low與high重合，此時所指位置為基準元素的正確位置
    # 將基準元素放到該位置
    alist[low] = mid

    # 對基準元素左邊的子序列進行快速排序
    quick_sort(alist, start, low-1)

    # 對基準元素右邊的子序列進行快速排序
    quick_sort(alist, low+1, end)


alist = [54,26,93,17,77,31,44,55,20]
quick_sort(alist,0,len(alist)-1)
print(alist)    

優(yōu)化1：基準元素不再選擇第一個元素，而是隨機選擇一個，這樣避免了有序數(shù)組，時間復雜度最壞為log(n2) 的情況

優(yōu)化2：三路快拍，把和基準元素相等的元素放在中間，比他小的在左邊，大的在右邊。這樣避免了重復元素過多的情況

Snip20171120_17.png

import random


def quicksort(arr, left, right):
    # 只有l(wèi)eft < right 排序
    if left >=right:
        return 
    #在列表里隨機選一個數(shù)來作為基準元素
    random_index = random.randint(left, right)
    #把基準元素和第一個元素交換
    arr[left], arr[random_index] = arr[random_index], arr[left]
    pivot = arr[left]
    #定義lt：小于v部分元素 的下標，初始是空的，因為arr[left]是基準元素
    lt = left # arr[left+1...lt] < v
    #gt 大于v 部分開始的下標，初始為空
    gt = right + 1 # arr[gt...right] > v
    i = left + 1 # arr[lt+1...i] == v
    #終止條件：下標i 和gt 遇到一起，說明都排完了
    while i < gt:
        if arr[i] < pivot:
            arr[i], arr[lt+1] = arr[lt+1], arr[i]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt-1] = arr[gt-1], arr[i]
            gt -= 1
        else:
            i += 1
     #最后把第一個元素（基準元素）放到等于v的部分
    arr[left], arr[lt] = arr[lt], arr[left]
    #遞歸排序
    quicksort(arr, left, lt-1)
    quicksort(arr, gt, right)