基本快速排序分析

以從小到大排序為例

• 選取一個主元（選取方式多樣）
• 利用主元，將序列分為兩個子序列，左側(cè)都比主元小，右側(cè)都比主元大。
• 對兩個子序列重復此操作

快排圖示

例如取第一個元素,代碼表示如下：

def qsort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        return qsort([x for x in arr[1:] if x < pivot]) + \
               [pivot] + \
               qsort([x for x in arr[1:] if x >= pivot])

優(yōu)化方案

1. 主元的選取
   上面的算法有很大的問題，對于升序或降序序列，效率很差，我優(yōu)化后的方式是主元取序列首中尾
   三個值取平均數(shù)，網(wǎng)上有些取三個值的中值的，我認為沒必要，為了效率還要將中值換到首或尾。
2. 序列中可能有一些和主元相等的元素，上面直接將其并入子序列中了，最好是將其和主元聚集
   在一起，子序列縮減幅度也會更快

這樣的話定義一個函數(shù)：

def getMidNum(list):
    return (list[0] + list[len(list) - 1] + list[len(list)/2])/3
def qsort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = getMidNum(arr)
        return qsort([x for x in arr[0:] if x < pivot]) + \
               [x for x in arr[0:] if x == pivot] + \
               qsort([x for x in arr[0:] if x > pivot])        
            

對比

分別構(gòu)造長度為10000的隨機數(shù)列表，升序列表，將序列表和等值列表，對比二者的表現(xiàn)