定義
快速排序（英語：Quick Sort）学搜，又稱劃分交換排序（partition-exchange sort）位谋，一種排序算法副签，最早由東尼·霍爾提出遥椿。在平均狀況下，排序n個項目要Ο(n log n)次比較淆储。在最壞狀況下則需要Ο(n2)次比較冠场，但這種狀況并不常見。事實上本砰，快速排序通常明顯比其他Ο(n log n)算法更快慈鸠，因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實現(xiàn)出來。
快速排序演示動畫1
算法步驟
快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。
步驟為：
- 從數(shù)列中挑出一個元素青团，稱為"基準(zhǔn)"（pivot）譬巫，
- 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面督笆，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）芦昔。在這個分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置娃肿。這個稱為分區(qū)（partition）操作咕缎。
- 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
遞歸的最底部情形料扰，是數(shù)列的大小是零或一凭豪，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去晒杈，但是這個算法總會結(jié)束嫂伞，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去拯钻。
偽代碼如下：
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))
}
快速排序演示動畫2
代碼實現(xiàn)（java）
/**
*
* @Title: quickSort
* @Description: 快速排序帖努，遞歸版
* @param: @param <E>
* @param: @param arr
* @param: @return
* @return: List<E>
* @throws
*/
public static <E extends Comparable<? super E>> List<E> quickSort(
List<E> arr)
{
if (!arr.isEmpty()) {
E pivot = arr.get(0); // This pivot can change to get faster results
List<E> less = new LinkedList<E>();
List<E> pivotList = new LinkedList<E>();
List<E> more = new LinkedList<E>();
// Partition
for (E i : arr) {
if (i.compareTo(pivot) < 0)
less.add(i);
else if (i.compareTo(pivot) > 0)
more.add(i);
else
pivotList.add(i);
}
// Recursively sort sublists
less = quickSort(less);
more = quickSort(more);
// Concatenate results
less.addAll(pivotList);
less.addAll(more);
return less;
}
return arr;
}
