人來人往，蜚短流長(zhǎng)，不求此生匆匆過，但求每日在成長(zhǎng)

快速排序嚴(yán)重依賴分區(qū)，分區(qū)部分完成就代表排序成功了一半

1、詳細(xì)思路見代碼注釋部分：

def quick_sort(l,low,high):
    '''
    分區(qū)的過程：
    low代表左指針，high代表右指針
    1、low會(huì)逐個(gè)向右移動(dòng)，遇到大于或等于基準(zhǔn)元素時(shí)，停止
    2、high會(huì)逐個(gè)向左移動(dòng)，遇到小于或等于基準(zhǔn)元素時(shí)，停止
    3、然后將兩指針?biāo)傅脑剡M(jìn)行交換
    4、重復(fù)上述步驟，直到兩指針重合，或者左指針在右指針的右邊
    5、最后將軸與左指針的值交換位置
    分區(qū)的目的：
    使基準(zhǔn)元素到正確的位置，然后再把基準(zhǔn)元素左右兩部分分別進(jìn)行排序
    '''
    if low >= high:  # 當(dāng)分出的子列表長(zhǎng)度為0或1時(shí)，就不會(huì)再遞歸下去了
        return
    pivot = l[high] # 設(shè)置初始的基準(zhǔn)元素
    inital_low = low # 將初始的low和high存儲(chǔ)一下
    inital_high = high
    while low < high:  # 步驟4
        while l[low]<pivot: # 步驟1
            low+=1
        while l[high] > pivot:  # 步驟2
            high -= 1
        l[low], l[high] = l[high], l[low] #步驟3
    l[low],pivot = pivot,l[low] # 步驟5
    
    '''
    分區(qū)后，將基準(zhǔn)元素左右兩部分分別進(jìn)行排序
    當(dāng)分出的子列表長(zhǎng)度為0或1時(shí)，就不會(huì)再遞歸下去了
    '''
    quick_sort(l, inital_low, low-1) #基準(zhǔn)左邊部分
    quick_sort(l, low+1, inital_high) #基準(zhǔn)右邊部分

    return l

if __name__=='__main__':
    l = [0,5,2,1,6,3]
    print(quick_sort(l, 0, len(l)-1))

2、效率分析
①分區(qū)步驟中，主要包含

• 比較：因?yàn)槊總€(gè)值都要和基準(zhǔn)元素進(jìn)行比較，所以比較次數(shù)為N；

• 交換：交換的次數(shù)則取決于數(shù)據(jù)的排列情況。一次分區(qū)里，交換最少會(huì)有1次，最多會(huì)有N / 2次，因?yàn)榧词顾性囟夹枰粨Q，我們也只是將左半部分與右半部分進(jìn)行交換，所以平均下來，粗略估算要進(jìn)行N/4次交換

  因此，分區(qū)步驟次數(shù)為N+N/4，大O計(jì)數(shù)法為O(N)

②因?yàn)榈确职l(fā)生了log N次，而每次都要對(duì)總共N個(gè)元素做分區(qū)，所以總步數(shù)為N×log N。

因此快速排序算法最佳時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度均為
最佳情況是在基準(zhǔn)元素每次都在子列表的中間
最壞情況是O(N^2)

由于快速排序在平均情況下表現(xiàn)優(yōu)異，于是很多編程語言自帶的排序函數(shù)都采用它來實(shí)現(xiàn)。

參考書目：
《數(shù)據(jù)結(jié)構(gòu)與算法圖解》作者：[美]杰伊·溫格羅