Quick Sort
快速排序
Tony Hoare 在1962年發明
優點:
1.分治算法
2.原地排序,意旨在原來數據區內進行重排(較省記憶體空間,類似插入排序,和歸類排序不同)
3.實用
1.分治算法
第一步:分解問題
快速排序本質上將數據分成幾份
舉例
將原Data按照某些特徵分成兩份
一份數據內值都比原Data來的小或少
一份數據內值都比原Data來的大或等於他
第二步
利用遞迴來處理兩個子數組的排序
第三步
兩子數組合併
Key
1,線性時間
時間複雜度θ(n)的子數組
舉例
Ex:{6,10,13,5,8,3,2,11} x<-6(主元)
i j->向右逐個掃描小於或等於主元(直到5小於6)
數組改變成{6,5,13,10,8,3,2,11}
i j->向右逐個掃描小於或等於主元(直到3小於6)
數組改變成{6,5,3,10,8,13,2,11}
i j->向右逐個掃描小於或等於主元(直到2小於6)
數組改變成{6,5,3,2,8,13,10,11}
i j->向右逐個掃描小於或等於主元
結束
最後2和6換
數組改變成{2,5,3,6,8,13,10,11}
左邊比6小<-| |->右邊比6大
分析
1.需假設其中的元素都是不相同
因為如果有重複會需要另外處理,例如去除重複
假設T(n)=最差的狀況下運行的時間
例如:數組已經排序過(正排序或逆排序)
你選擇的主元素有可能都比全部數組小或大
假設一邊都沒有元素
T(n)=T(0)+T(n-1)+θ(n)
=θ(1)+T(n-1)+θ(n)
=T(n-1)+θ(n)
=θ(n²) (因為是等差級數)
最差狀況舉例
T(n)=T(0)+T(n-1)+cn (cn展開出來)
= cn
/ \
T(0) T(n-1)
= cn
/ \
T(0) c(n-1)
/ \
T(0) T(n-2)
= cn
/ \
θ(1) =T(0) c(n-1)
/ \
θ(1)=T(0) T(n-2)
/ \
θ(1) =T(0) ......
\
θ(1)
所以樹的高度是多少?(n=?)
Ans: 高度=n
n
θ(ΣCK)
k=1
=θ(n²)
總量:
T(n)=θ(n) +θ(n²) =θ(n²)
最優情況:
不能代表什麼,因為不能保證最優情況
但能幫助直觀了解
例如:劃分在最中央
T(n)=2T(n/2)+θ(n)
=θ(nlgn) (非常快速)
如果劃分是在1/10(n/10) ,9/10((9n/10))呢?
T(n)=T(n/10)+T(9n/10)+θ(n) (假設θ(n)<=cn)
=θ(nlgn) (非常快速)
T(n)= cn =cn
/ \
T(1/10) T(9/10) =cn
/ \
..... ....... <=cn(因為左邊可能會沒有)
/ \
θ(1) θ(1) 總和: θ(nlgn )= cnlog ₁ ₀n +θ(n) :下限 <=T(n)<=上限:cn(log ₁ ₀ ⁄ ₉n)+θ(n) =θ(nlgn)
目前參照上例會發現左邊到底層會比右邊高
那左邊到底層的長度為log ₁ ₀n (log以10為底的n,因為左邊每次減少1/10,需要減少多少次到達1,以10為底數的定義)
那右邊到底層的長度為log ₁ ₀ ⁄ ₉n (log以10/9為底的n,因為左邊每次減少9/10,需要減少多少次到達1,以10為底數的定義)
如果最優情況和最壞情況交替出現
L(n)=2U(n/2)+θ(n) 最優(考慮下一步是最壞)
U(n)=L(n-1)+θ(n) 最壞(考慮下一步是最優)
代換法
L(n)=2(L((n/2-1)+θ(n))+θ(n/2)
=2L(n/2-1)+θ(n)
=θ(nlgn) (代表是最優,幸運)
如何確保總是最優?
隨機化快速排序
好處
1.運行時間不依賴輸入序列的順序
2.無須對輸入序列的分布做任何假設
3.沒有任何一種輸入順序會造成最差運行效率
4.最差狀況是由隨機數產生器來決定
分析
參考網址
達人
