快速排序

分解：數組A[p..r]被分成兩個子數組A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每一個元素都小於等於A[q]，而A[q]也小於等於A[q+1..r]中的每一個元素。

解決：通過遞歸調用快速排序，對子數組A[p..q-1]和A[q+1..r]進行排序。

合併：因為子數組都是原址排序，因此不需要合併，數組已經有序。

Quicksort(A,p,r)if p < r q = Partition(A,p,r) Quicksort(A,p,q-1) quicksort(A,q+1,r)

Partition(A,p,r)x = A[r]i = p -1for j = p to r-1 if A[j] <= x i = i + 1 exchange A[i] with A[j]exchange A[i] with A[j]return i+1

#pythondef partition(A,p,r): x = A[r] i = p -1 for j in range(p,r): if A[j] <= x: i = i + 1 A[i],A[j] = A[j],A[i] A[i+1],A[r] = A[r],A[i+1] return i+1def quick_sort(A,p,r): if p < r: q = partition(A,p,r) quick_sort(A,p,q-1) quick_sort(A,q+1,r)

推薦閱讀：