快速排序圖解

快速排序是一種基於分治思想的排序算法，效率非常高。它通過在序列中尋找一個主元，將小於主元的元素放在左邊，大於主元的元素放在右邊，然後在左右子序列中分別遞歸地應用快速排序。下面將從算法流程、時間複雜度、優缺點、代碼示例幾個方面詳細介紹快速排序。

一、算法流程

1、選取主元

首先在序列中選擇一個主元，可以選擇第一個元素或隨機選擇一個元素作為主元。

function choose_pivot(seq):
    return seq[0]

2、分區

將序列中的元素分為兩部分，一部分是小於主元的元素，另一部分是大於主元的元素。可以用兩個指針i,j來實現分區。

function partition(seq, pivot):
    i, j = 0, len(seq)-1
    while i <= j:
        while seq[i] < pivot:
            i += 1
        while seq[j] > pivot:
            j -= 1
        if i <= j:
            seq[i], seq[j] = seq[j], seq[i]
            i += 1
            j -= 1
    return i

3、遞歸排序

對左右兩個子序列分別遞歸地應用快速排序。

function quicksort(seq):
    if len(seq) <= 1:
        return seq
    pivot = choose_pivot(seq)
    index = partition(seq, pivot)
    left_seq = quicksort(seq[:index])
    right_seq = quicksort(seq[index:])
    return left_seq + right_seq

二、時間複雜度

快速排序的時間複雜度為O(nlogn)或O(n^2)。

在最好的情況下，每次分區都能將序列均勻地分成兩部分，遞歸樹的深度為log2n，每一層需要進行n次操作，因此時間複雜度為O(nlogn)。

在最壞的情況下，每次分區都只能將序列分成一部分和另一部分，遞歸樹的深度為n-1，每一層需要進行n次操作，因此時間複雜度為O(n^2)。但是在實際應用中，最壞情況發生的概率比較小。

三、優缺點

優點：

1、效率高，在大多數情況下比其他排序算法效率更高。

2、空間複雜度低，只需要一個額外的空間來存儲主元的值。

3、易於實現。

缺點：

1、當序列中存在大量相同的元素時，快速排序的效率會比較低。

2、不穩定性排序，排序後相同元素的順序可能會改變。

四、代碼示例

下面是Python代碼實現：

def choose_pivot(seq):
    return seq[0]

def partition(seq, pivot):
    i, j = 0, len(seq)-1
    while i <= j:
        while seq[i] < pivot:
            i += 1
        while seq[j] > pivot:
            j -= 1
        if i <= j:
            seq[i], seq[j] = seq[j], seq[i]
            i += 1
            j -= 1
    return i

def quicksort(seq):
    if len(seq) <= 1:
        return seq
    pivot = choose_pivot(seq)
    index = partition(seq, pivot)
    left_seq = quicksort(seq[:index])
    right_seq = quicksort(seq[index:])
    return left_seq + right_seq

seq = [5, 1, 9, 3, 7, 4, 8, 6, 2]
print(quicksort(seq))