Quick Sort 利用快速排序法解決重複元素排序
快速排序算法擁有最佳計算複雜度 O(n log n)， 但在特殊情況下會退化成 O(n^2)。 其中一個特殊情況就是大量重複元素的排列問題。 解決問題前， 先介紹快速排序法的實現。 假設你得到一隨機一維陣列要做升冪排序， 最終的結果需要是這樣： 選定隨機陣列最左側為 pivot ，pivot 為 L指標、最右側為 R指標。 首先先判斷終止條件：R 的 index 是否等於 L 的 index？ 等於的話就將 pivot 的 值 與 R、L 的值交換，進行下一循環。 R 的 index 不等於 L 的 index的話繼續尋找： R指標啟動尋找小於等於 pivot 的值，L 尋找大於 pivot 的值，找到就鎖定。 若 R 的 index != L 的 index，則兩者的值交換。 以此類推，當 R 的 index == L 的 index 時，交換 pivot 與 R 的值。 並以交換點為準，分割左邊右邊兩個子循環。 這邊可以順便推導為什麼 quick sort 的計算複雜度為 O(n log n)， 因為相較於 bubble sort 中每個 pivot 要比較 n-1 個元素， quick sort 在第二次以後的理想狀況每個 pivot 只需比較 (n/2)^m個元素 （m=排序次數-1）。 所以最佳計算複雜度才會是 O(n log n) // n個 pivot 乘上該次比較元素量。 但是齁，人算不如天算。 有時候就會遇到很棘手的情況，讓 quick sort 一點都不 quick。 主要分為兩種： 已排序數列。 存在著大量重複元素的數列。 1. 已排序數列。 已排序數列的問題在於分割的左右子陣列不平衡， 導致需要搜尋的元素趨近於 n。 如此一來計算複雜度便會退化成 O(n^2) 解法：把數列打亂即可解決這個問題。 2.存在著大量重複元素的數列。 這個就比較麻煩了，因為打亂也解決不了（＃。 這個問題在於要搜尋相等於 pivot 的重複數， 兩數之間總共有三種關係嘛：大於、等於、小於。 之前的方法一直把等於的方法掛在 L指標上面做， 解決問題的核心精神是特別考慮等於的情況處理。 重複數處理...