交換排序之快速排序

快速排序

　　快速排序（Quick Sort）通過一趟排序將待排記錄分割成獨立的兩部分其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小則可分別對這兩部分記錄繼續進行排序以達到整個序列有序

快速排序三個步驟

　　分解（Divide）將原問題分解為若干個子問題此步驟亦稱為劃分
　　求解（Conquer）遞歸地解各子問題若子問題的規模足夠小則直接求解
　　組合（Combine）將各子問題的解組合成原問題的解

一趟快速排序采用從兩頭向中間夾入比較同時交換與基准鍵值逆序的結點

快速排序算法

　　快速排序的最壞時間復雜度為O(n)最好時間復雜度為O(nlgn)平均時間復雜度為O(nlgn)
 
　　快速排序方法是不穩定的

From:http://tw.wingwit.com/Article/program/sjjg/201311/23839.html