快速排序（英語(yǔ)：Quicksort），又稱劃分交換排序（partition-exchange sort），通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

步驟為：

從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot），
重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。
遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個(gè)算法總會(huì)結(jié)束，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。

lista = [20,5,15,47,58,25,23,26,14]

def quick_sort(lista, first, last):
    # 遞歸的退出條件
    if first >= last:
        return
    # 設(shè)定起始元素為要尋找位置的基準(zhǔn)元素
    mid_value = lista[first]
    # low為序列左邊的由左向右移動(dòng)的游標(biāo)
    # high為序列右邊的由右向左移動(dòng)的游標(biāo)
    low = first
    hight = last

    while low < hight:
        # 當(dāng)hight位的值大于mid_value的值則一直向左移動(dòng)
        while low < hight and lista[hight] >= mid_value:
            hight -= 1
        # 停止移動(dòng)要么low與hight重合,要么到了hight位值小于mid_value
        lista[low] = lista[hight]

        while low < hight and lista[low] < mid_value:
            low += 1
        lista[hight] = lista[low]
        # hight -= 1
    # 退出循環(huán)后，low與high重合，此時(shí)所指位置為基準(zhǔn)元素的正確位置
    # 將基準(zhǔn)元素放到該位置
    lista[low] = mid_value
    # 在做遞歸的時(shí)候沒(méi)有用切片,是為了保證在做多次遞歸的時(shí)候操作排序的永遠(yuǎn)只會(huì)是這一個(gè)列表
    # 先對(duì)標(biāo)志位左邊的先進(jìn)行排序
    quick_sort(lista, first, low-1)
    # 再對(duì)標(biāo)志位右邊的先進(jìn)行排序
    quick_sort(lista, low+1, last)

    return lista
print(quick_sort(lista,0, len(lista)-1))

image.png

時(shí)間復(fù)雜度

最優(yōu)時(shí)間復(fù)雜度：O(nlogn)
最壞時(shí)間復(fù)雜度：O(n2)
穩(wěn)定性：不穩(wěn)定