快速排序

對于包含N個數的輸入數組來說，快速排序是一種最壞情況時間複雜度為O(n2)的排序算法。雖然最壞情況時間複雜度很差，但是快速排序通常是實際排序應用中最好的選擇，因為它的平均性能非常好：它的期望時間複雜度是O(nlgn)，而且O(nlgn)中的隐藏因子非常小。另外，它還能夠進行原址重排，甚至在虛存環境中也能很好地工作。

對數組A[p..r]進行快速排序的三步分治過程:

分解 

數組A[p..r]被劃分為兩個(可能為空)子數組A[p..q-1]和A[q+1..r]。其中使得數組A[p..q-1]中的每個元素都小于等于A[q],而A[q]小于等于數組A[q+1..r]中的每個元素。

計算下标q也是劃分過程的部分

解決

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

合并

因為子數組都是原址排序，是以不需要合并操作，數組A[p..r]已經有序

下面給出快速排序實作的僞代碼

為了排序一個數組A的全部元素，初始調用是quickSort(A,1,A.length).

第3步是很重要的一步，它實作了對子數組的原址重排，可以有很多實作方法，下面給出一種，僞代碼為:

下面給出示例代碼

View Code