# 快速排序 快速排序得名于實際應用的高效率,它幾乎是排序最快的算法，入選20世紀十大算法之一。與歸并排序一樣，快速排序用了分治法的思想，并且都是原址排序。 核心：對于數X，假如你知道假如你知道小于它的個數，大于它的個數，那么你就知道了X的位置。 步驟： 1. 選取一個分界數，大于分界數的放在右邊，小于分界數放在左邊。 2. 對于分界數左邊和右邊，分別遞歸調用步驟1，直到分界數左右邊只有一個數，也可以為空 3. 合并得到結果，因為每一次調用，分界數肯定在正確的位置，直到所有遞歸結束，所有的數就剛好在正確的位置，就不需要花時間搶合并，這就是原址排序 ~~~ Partition(A,p,r)//以A[r]作為分界數，進行劃分 x=A[r] i=0 for j=p to r-1 if(A[j]<=x) i=i+1 exchance A[i] with A[j] exchance A[i+1]with A[r] return i+1 QuickSort(A,p,r)//當一個數組，或子數組只有一個元素時，停止遞歸重排 If p<r q= Partition(A,p,r) QuickSort(A,p,q-1) QuickSort(A,q+1,r) ~~~ **最壞情況：** 當數組劃分越多次，調用遞歸的次數最多，也就是當數組所有的數相等時，運行時間最糟糕。時間復雜度為O（n^2）；特別地：當數組已經排序好，也是最壞情況，而這時插入排序的時間復雜度為O（n）；雖然是這樣，但是這種情況卻是很少發生，因而其平均性能很好 **最好情況：** 當每次劃分都是最平衡的劃分,快速排序的性能最好,時間復雜度為O(n*log2(n)),平均運行時間復雜度也為O(n*log2(n))