快速排序演算法
基本思想：被排序陣列為A，用陣列首元素作為標準將A分成前后兩部分，比首元素小的元素構成陣列的前部分，比首元素大的部分構成陣列的后部分，這兩部分構成兩個新的子問題，演算法接著對這兩個陣列進行遞回，
Quicksort(A,p,r) //p,r分別為陣列A的首元素和尾元素的下標
輸入：陣列A[p..r]，1<=p<=r<=n
輸出：從A[p]到A[r]按遞增順序排好序的陣列A
if p<r
then q <- Partition(A,p,r) //劃分陣列，找到首元素A[p]在排好序后的位置q
A[p] <-> A[q]
Quicksort(A,p,q-1)
Quicksort(A,q+1,r)
Partition是劃分的程序
x <- A[p]
i <- p+1
j <- r+1
while true do
repeat j <- j-1
until A[j] <= x
repeat i <- i+1
until A[i] > x
if i < j
then A[i] <-> A[j]
else return j
下面舉一個例子
演算法的時間復雜度分析
- 每個元素都要和首元素進行一次比較（在i，j相遇位置附近的元素可能比較2次），所以劃分程序的作業量是O(n)，
- 兩個子問題遞回呼叫的作業量
快速排序演算法的各種情況分析
1.
均等劃分子問題
先看均等劃分的例子，如果每次劃分得到的子問題大小都相等，即每個子問題的規模都等于n/2，那么在當前實體下時間復雜度函式的遞推方程是：
\[\left\{ \begin{array}{lr} T(n)=2T(n/2)+O(n) & \\ T(1)=0& \end{array} \right. \]
根據主定理，該方程的解\(T(n)=O(nlogn)\)，這是一種比較好的情況，
2.
子問題規模不同，但遵從一定比例
即使子問題規模不一樣，但兩個子問題的規模遵從一定的比例，比如1:9，那么時間復雜度函式的遞推方程為：
\[\left\{ \begin{array}{lr} T(n)=T(n/10)+T(9n/10)+O(n) & \\ T(1)=0& \end{array} \right. \]
c是常數
這棵樹不均衡，從樹根到最左邊樹葉的路徑最短，在這條路徑上，每層的子節點的值是父節點值的1/10，設樹根是第0層，每層為第k層，
\(\frac{1}{10}\)^k^n代表當前第k層的值，即子問題規模，
\(\frac{1}{10}\)^0^n=n，代表第0層值為n，
當\(\frac{1}{10}\)^k^*n=1，即子問題規模為1，到達樹葉時，k=\(\log\)~10~(\(x\))，
同理得到最右邊路徑長度是log~10/9~n，為了表示時間漸進的上界，不妨取最長路徑作為樹的層次，即所有節點的數值之和為
T(n) = c\(n\log\)~10/9~\(n\) = O(\(n\log(n)\))
這說明，即使子問題規模不均衡，但是只要比例一定，快速排序演算法的時間復雜度仍舊是\(O(n\log(n))\)，
3.
下面介紹極端不均衡的情況
即劃分后兩個子問題的規模一個是0，另一個是\(n-1\)的情況，當陣列元素是按從小到大正排序或從大到小逆排列時，就會呈現這種劃分，
\[\left\{ \begin{array}{lr} W(n)=W(n-1)+O(n) & \\ W(1)=0& \end{array} \right. \]
根據迭代歸納，此時\(W(n)=O(n^2)\)
但最壞情況出現的概率很低，它的平均性能還是不錯的，
4.
平均情況
假設交換后，陣列A的首元素在排好序后處在\(n\)個位置中的任何位置都是等可能的，即它處在任何位置的概率都是\(1/n\)，如果它處在位置\(i\)（\(i\)=1,2,...,\(n\)），那么劃分后的兩個子問題規模分別是\(i-1\)和\(n-1\)，考慮到\(T(0)=0\)，因此可以得到
當把\(O(n)\)看作\(n-1\)時，這個方程的解是\(T(n)=O(nlogn)\)，
對于排序問題，平均情況下效率最高的演算法就是時間復雜度為\(O(nlogn)\)的演算法，在這個情況下，快速排序演算法是平均情況下效率最高的演算法之一，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/69644.html
標籤：其他
上一篇：POJ - 1847 Tram
下一篇：找出"吸血鬼數"(Java)