快速排序(quick sort)

03-07

快速排序堆包括n個數的輸入數組，最壞情況運行時間為 $Theta(n^2)$ ,平均運行時間為 $Theta(nlg n)$ ，且 $Theta(nlg n)$ 記號中隱含的常數因子很小，因此通常是用於排序的最佳的實用選擇。本文介紹快速排序演算法。

演算法描述

快速排序演算法基於分治法(divide and conquer). 下面是對一個典型子數組 $A[p..r]$ 排序的分支過程進行解讀。

分解：數組 $A[p..r]$ 被分為兩個子數組 $A[p..q-1]$ 和 $A[q+1..r]$ ，使得 $A[p..q-1]$ 中的元素小於 $A[q]$ ， $A[q+1..r]$ 中的元素大於 $A[q]$
解決：通過遞歸調用快速排序，對子數組 $A[p..q-1]$ 和 $A[q..r]$ 進行排序
合併：這時得到的額兩個子數組是就地排序的，因此合併不需要操作，整個數組 $A[p..r]$ 已經排序(in-place)

在分解子數組的過程中可以選擇任意的切分點，下面的例子中，第一次切分為3，第二次為2、4，第三次為1.這個可以自行選擇

演算法實現

def quick_sort(A,p,r): """ A: list p: int r: int """ if p < r: mid = partition(A, p ,r) quick_sort(A,p,mid-1) quick_sort(A,mid,r)def partition(A, p, r): """ find the partition index """ x = A[r] i = p - 1 j = p while j <= r - 1: if A[j] < x: i = i + 1 A[i], A[j] = A[j], A[i] j = j + 1 A[i+1], A[r] = A[r], A[i+1] return i + 1

在實現中，我們採用了最右點作為切分點，並且進行了in-place的就地排序，因此merge不需要做什麼事情。

測試如下

if __name__ == "__main__": A=[1,4,3,6,2] quick_sort(A,0,len(A)-1) print A[1, 2, 3, 4, 6]