Contents
  1. 1. 概念
  2. 2. Pivot的挑選
  3. 3. quicksort變型版
  4. 4. 時間複雜度
  5. 5. 空間複雜度
  6. 6. 穩定性
  7. 7. Code

概念

從數列裡挑選一個“基準”(pivot),大於基準值的放一堆,小於的放一堆,再分別對各堆去找基準,又分成兩堆(divide & conquer),依照相同的概念一直循環,最後完成排序。

Pivot的挑選

數列中的第一個,或最中間的數,也可以隨機挑選。以這邊的例子來說,In-Place version是選中間的數,Not-in-place version是選第一個。
pivot的選擇會影響演算法的效能,舉例來說,若pivot選擇第一個,但該數列已經是排序好的序列,而且順序剛好都相反,則會發生效能最差的情況。

quicksort變型版

quicksort有很多不同的版本,像是multi-pivot quicksort、external quicksort、three-way radix quicksort等等。而Java 7中,基本型態的陣列(array)的sort就是以multi-pivot quicksort實作的,之後有時間再研究看看。

時間複雜度

Best : O(nlog n)
Average : O(nlog n)
Worst : O(n2)

空間複雜度

In-place : O(log n)
Not-in-place : O(n)

穩定性

In-place : 不穩定
Not-in-place : 穩定

Code

See my code on github.

參考資料:
Quicksort wiki
Sorting algorithm wiki