快速排序算法是基于分治策略的另一個排序算法。其基本思想是，對于輸入的字數(shù)組a[p:r]，按以下3個步驟進行排序：
（1）分解：以a[p]為基準元素將a[p:r]劃分成3段a[p:q-1],a[q]和a[q+1:r]，使得a[p:q-1]中任何元素小于等于a[q]，a[q+1:r]，中的任何元素大于等于a[q]。下標q在劃分過程中確定
（2）遞歸求解：通過遞歸調用快速排序算法，分別對a[p:q-1]和a[q+1:r]進行排序
（3）合并：在a[p:q-1]和a[q+1:r]已經(jīng)排好序的情況下，不需要執(zhí)行任何運算，a[p:r]就已排好序
平均算法復雜度O(nlogn)
標簽：
快速排序
分
算法
策略
上傳時間：
2016-07-09
上傳用戶：wuyuying
