quick sort

quick sort 中文譯為快速排序演算法,在comparison sort 中算是最快的演算法,其平均複雜度可以到$O(nlog\ n)$,其原理為利用分治法(divide and conquer), 假設現有一數列等待我們來排序,我們可在數列中選擇任一數字做為支點(pivot),將比支點小的數分成一堆,比支點大的數分成一堆,再遞迴處理,假設每次都可以把數列平分,則其複雜度算式可寫為 $T(n)=2*T(\frac{n}{2})+O(n)$,其中$O(n)$為分類所需的時間,如此一來,複雜度為$O(nlog\ n)$,然而事情總是不這麼美好QQ,如果不小心pivot沒有選好,則可能每次分群,都有一群沒有任何數,如此一來,$T(n)=T(n-1)+O(n)$,其複雜度退化到$O(n^2)$,實在太慢了@@, 於是聰明的電腦科學家為了避免這個問題,於是引進了隨機選支點的方法,如此一來,平均複雜度可以達到$O(nlog\ n)$, oh YA!!!




至於如何用pivot來分群呢,就是一個小技巧了XD,其原理為將隨機選中的pivot和最左邊或最右邊的數互換,接著利用兩個變數作為指標,其中一個變數表示其左邊的數都小於pivot,另一個變數表示目前確認到哪一個數,若確認到的數比pivot小,則將那個數和第一個變數指到的數互換,如此一直移動第二個變數,最後再將pivot和第一個指標指到的數互換,大功告成!!!
參考資料:
1. MIT ocw
2. coursera
3. introduction to algorithms