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

步驟為：

從數(shù)列中挑出一個元素，稱為"基準"（pivot），
重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)結束之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。
遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序。
遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個算法總會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。

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

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

    while low < hight:
        # 當hight位的值大于mid_value的值則一直向左移動
        while low < hight and lista[hight] >= mid_value:
            hight -= 1
        # 停止移動要么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重合，此時所指位置為基準元素的正確位置
    # 將基準元素放到該位置
    lista[low] = mid_value
    # 在做遞歸的時候沒有用切片,是為了保證在做多次遞歸的時候操作排序的永遠只會是這一個列表
    # 先對標志位左邊的先進行排序
    quick_sort(lista, first, low-1)
    # 再對標志位右邊的先進行排序
    quick_sort(lista, low+1, last)

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

image.png

時間復雜度

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