# 快速排序

## 演算法

1. 挑选基准值：從數列中挑出一個元素，稱為「基準」（pivot），
2. 分割：重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面（与基准值相等的數可以到任何一邊）。在這個分割結束之後，对基准值的排序就已经完成，
3. 递归排序子序列：递归地将小於基准值元素的子序列和大於基准值元素的子序列排序。

function quicksort(q)
{
var list less, pivotList, greater
if length(q) ≤ 1
return q
else
{
select a pivot value pivot from q
for each x in q except the pivot element
{
if x < pivot then add x to less
if x ≥ pivot then add x to greater
}
add pivot to pivotList
return concatenate(quicksort(less), pivotList, quicksort(greater))
}
}

### 原地（in-place）分割的版本

function partition(a, left, right, pivotIndex)
{
pivotValue = a[pivotIndex]
swap(a[pivotIndex], a[right]) // 把pivot移到結尾
storeIndex = left
for i from left to right-1
{
if a[i] <= pivotValue
{
swap(a[storeIndex], a[i])
storeIndex = storeIndex + 1
}
}
swap(a[right], a[storeIndex]) // 把pivot移到它最後的地方
return storeIndex
}

procedure quicksort(a, left, right)
if right > left
select a pivot value a[pivotIndex]
pivotNewIndex := partition(a, left, right, pivotIndex)
quicksort(a, left, pivotNewIndex-1)
quicksort(a, pivotNewIndex+1, right)

## 正規分析

${\displaystyle T(n)=O(n)+2T(n/2)}$

${\displaystyle T(n)=O(n)+T(1)+T(n-1)=O(n)+T(n-1)}$

### 平均複雜度

${\displaystyle C(n)=n-1+{\frac {1}{n}}\sum _{i=0}^{n-1}(C(i)+C(n-i-1))=2n\ln n=1.39n\log _{2}n}$

### 空間複雜度

${\displaystyle \sum _{i=0}^{\infty }{\frac {n}{2^{i}}}=2n}$

${\displaystyle \sum _{i=0}^{n}(n-i+1)=\Theta (n^{2})}$

## 參考

• Hoare, C. A. R. "Partition: Algorithm 63," "Quicksort: Algorithm 64," and "Find: Algorithm 65." Comm. ACM 4, 321-322, 1961
• R. Sedgewick. Implementing quicksort programs, Communications of the ACM, 21(10):847-857, 1978.
• David Musser. Introspective Sorting and Selection Algorithms, Software Practice and Experience vol 27, number 8, pages 983-993, 1997
• A. LaMarca and R. E. Ladner. "The Influence of Caches on the Performance of Sorting." Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997. pp. 370–379.
• Faron Moller. Analysis of Quicksort. CS 332: Designing Algorithms. Department of Computer Science, University of Wales Swansea.
• Steven Skiena. Lecture 5 - quicksort. CSE 373/548 - Analysis of Algorithms. Department of Computer Science. SUNY Stony Brook.

## 註腳

1. David M. W. Powers. Parallelized Quicksort with Optimal Speedup页面存档备份，存于互联网档案馆）. Proceedings of International Conference on Parallel Computing Technologies. Novosibirsk. 1991.