<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Quick Sort - 快速排序 -------- #### 問題 用快速排序對長度為$$ n $$的無序序列$$ s $$進行排序。 #### 解法 本問題對無序序列$$ s $$進行升序排序，排序后$$ s $$是從小到大的。 將長度為$$ n $$的序列$$ s $$，選取最左邊的值作為$$ pivot $$，將剩余部分分為$$ left $$和$$ right $$兩個部分，$$ left $$和$$ right $$是無序的，且$$ left $$中的所有元素$$ \forall x \le pivot $$（其中$$ x \in left $$），$$ right $$中的所有元素$$ \forall y \le pivot $$（其中$$ y \in right $$）。 初始時$$ left $$和$$ right $$兩個部分都是空的，分別從數組$$ s $$的左右兩邊向中間推進。例如下圖中的數組：  初始時設置$$ pivot = s[0] = 45 $$，$$ low = 0 $$，$$ high = n-1 $$。從$$ high $$開始，向左搜索到第一個元素$$ s[high] \lt pivot $$（$$ high = n-1 $$），該元素不符合$$ right $$的性質，因此將$$ s[high] $$移動到$$ s[low] $$（$$ s[low] = s[high] $$）。  再從$$ low $$開始，向右搜索到第一個元素$$ s[low] \gt pivot $$（$$ low = 1 $$），該元素不符合$$ left $$的性質，因此將$$ s[low] $$移動到$$ s[high] $$（$$ s[high] = s[low] $$）。  重復上面的操作，直到$$ low = high $$，這時的$$ low $$和$$ high $$的位置即為$$ left $$和$$ right $$的中間位置，將$$ pivot $$移動到該位置（$$ s[low] = pivot $$），就完成了一輪排序。$$ left $$和$$ right $$內部仍然是無序的，把它們也當作一個數組，遞歸的進行排序即可。 對于長度$$ n $$的序列$$ s $$，每一輪放置所需要的時間為$$ O(n) $$，總共需要$$ log_{2} n $$輪，該算法的時間復雜度為$$ O(n \cdot log_{2}n) $$。 -------- #### 源碼 [QuickSort.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Sort/QuickSort.h) [QuickSort.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Sort/QuickSort.cpp) #### 測試 [QuickSortTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Sort/QuickSortTest.cpp)