快速排序
 使用快速排序法對一列數字進行排序的過程 |
|
| 分類 | 排序算法 |
|---|---|
| 數據結構 | 不定 |
| 最差時間復雜度 | Θ(n2) |
| 最優時間復雜度 | Θ(nlog n) |
| 平均時間復雜度 | Θ(nlog n) |
| 最差空間復雜度 | 根據實現的方式不同而不同 |
| 最佳算法 | 有时是 |
快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他Ο(n log n) 演算法更快，因為它的內部循环（inner loop）可以在大部分的架構上很有效率地被實作出來，且在大部分真實世界的資料，可以決定設計的選擇，減少所需時間的二次方項之可能性。
目录 |
[编辑] 演算法
快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。
步驟為：
- 從數列中挑出一個元素，稱為 "基準"（pivot），
- 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分割結束之後，該基準就處於數列的中間位置。這個稱為分割（partition）操作。
- 递归地（recursive）把小於基准值元素的子數列和大於基准值元素的子數列排序。
遞迴的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞迴下去，但是這個演算法總會結束，因為在每次的迭代（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))
}
[编辑] 原地(in-place)分割的版本
上面簡單版本的缺點是，它需要Ω(n)的額外儲存空間，也就跟归并排序一樣不好。額外需要的記憶體空間配置，在實際上的實作，也會極度影響速度和快取的效能。有一個比較複雜使用原地（in-place）分割算法的版本，且在好的基準選擇上，平均可以達到O(log n)空間的使用複雜度。
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
這是原地分割演算法，它分割了標示為 "左邊（left）" 和 "右邊（right）" 的序列部份，藉由移動小於a[pivotIndex]的所有元素到子序列的開頭，留下所有大於或等於的元素接在他們後面。在這個過程它也為基準元素找尋最後擺放的位置，也就是它回傳的值。它暫時地把基準元素移到子序列的結尾，而不會被前述方式影響到。由於演算法只使用交換，因此最後的數列與原先的數列擁有一樣的元素。要注意的是，一個元素在到達它的最後位置前，可能會被交換很多次。
一旦我們有了這個分割演算法，要寫快速排列本身就很容易：
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)
這個版本經常會被使用在命令式語言中，像是C語言。
[编辑] 競爭的排序演算法
快速排序是二叉查找树（二元搜尋樹）的一個空間最佳化版本。不以循序地把項目插入到一個明確的樹中，而是由快速排序組織這些項目到一個由遞迴呼叫所意含的樹中。這兩個演算法完全地產生相同的比較次數，但是順序不同。
快速排序的最直接競爭者是堆排序（Heapsort）。堆排序通常比快速排序稍微慢，但是最壞情況的執行時間總是O(n log n)。快速排序是經常比較快，除了introsort變化版本外，仍然有最壞情況效能的機會。如果事先知道堆排序將會是需要使用的，那麼直接地使用堆排序比等待 introsort 再切換到它還要快。堆排序也擁有重要的特點，僅使用固定額外的空間（堆排序是原地排序），而即使是最佳的快速排序變化版本也需要Θ(log n)的空間。然而，堆排序需要有效率的隨機存取才能變成可行。
快速排序也與归并排序（Mergesort）競爭，這是另外一種遞迴排序算法，但有壞情況O(n log n)執行時間的優勢。不像快速排序或堆排序，归并排序是一個穩定排序，且可以輕易地被採用在链表（linked list）和儲存在慢速存取媒體上像是磁碟儲存或網路連接儲存的非常巨大數列。儘管快速排序可以被重新改寫使用在鍊串列上，但是它通常會因為無法隨機存取而導致差的基準選擇。归并排序的主要缺點，是在最佳情況下需要Ω(n)額外的空間。
[编辑] 正規的分析
從一開始快速排序平均需要花費O(n log n)時間的描述並不明顯。但是不難觀察到的是分割運算，陣列的元素都會在每次迴圈中走訪過一次，使用O(n)的時間。在使用結合（concatenation）的版本中，這項運算也是O(n)。
在最好的情況，每次我們執行一次分割，我們會把一個數列分為兩個幾近相等的片段。這個意思就是每次遞迴调用處理一半大小的數列。因此，在到達大小為一的數列前，我們只要作 log n 次巢狀的调用。這個意思就是调用樹的深度是O(log n)。但是在同一階層的兩個程序调用中，不會處理到原來數列的相同部份；因此，程序调用的每一階層總共全部僅需要O(n)的時間（每個调用有某些共同的額外耗費，但是因為在每一階層僅僅只有O(n)個调用，這些被歸納在O(n)係數中）。結果是這個演算法僅需使用O(n log n)時間。
另外一個方法是為T(n)設立一個遞迴關係式，也就是需要排序大小為n的數列所需要的時間。在最好的情況下，因為一個單獨的快速排序调用牽涉了O(n)的工作，加上對n/2大小之數列的兩個遞迴调用，這個關係式可以是：
- T(n) = O(n) + 2T(n/2)
解決這種關係式型態的標準数学归纳法技巧告訴我們T(n) = O(n log n)。
事實上，並不需要把數列如此精確地分割；即使如果每個基準值將元素分開為 99% 在一邊和 1% 在另一邊，调用的深度仍然限制在 100log n，所以全部執行時間依然是O(n log n)。
然而，在最壞的情況是，兩子數列擁有大各為 1 和 n-1，且调用樹（call tree）變成為一個 n 個巢狀（nested）呼叫的線性連串（chain）。第 i 次呼叫作了O(n-i)的工作量，且
遞迴關係式為：
- T(n) = O(n) + T(1) + T(n - 1) = O(n) + T(n - 1)
這與插入排序和选择排序有相同的關係式，以及它被解為T(n) = O(n2)。
[编辑] 亂數快速排序的期望複雜度
亂數快速排序有一個值得注意的特性，在任意輸入資料的狀況下，它只需要O(n log n)的期望時間。是什麼讓隨機的基準變成一個好的選擇？
假設我們排序一個數列，然後把它分為四個部份。在中央的兩個部份將會包含最好的基準值；他們的每一個至少都會比25%的元素大，且至少比25%的元素小。如果我們可以一致地從這兩個中央的部份選出一個元素，在到達大小為1的數列前，我們可能最多僅需要把數列分割2log2 n次，產生一個 O(nlogn)演算法。
不幸地，亂數選擇只有一半的時間會從中間的部份選擇。出人意外的事實是這樣就已經足夠好了。想像你正在翻轉一枚硬幣，一直翻轉一直到有 k 次人頭那面出現。儘管這需要很長的時間，平均來說只需要 2k 次翻動。且在 100k 次翻動中得不到 k 次人頭那面的機會，是像天文數字一樣的非常小。藉由同樣的論證，快速排序的遞迴平均只要2(2log2 n)的呼叫深度就會終止。但是如果它的平均呼叫深度是O(log n)且每一階的呼叫樹狀過程最多有 n 個元素，則全部完成的工作量平均上是乘積，也就是 O(n log n)。
[编辑] 平均複雜度
即使如果我們無法隨機地選擇基準數值，對於它的輸入之所有可能排列，快速排序仍然只需要O(n log n)時間。因為這個平均是簡單地將輸入之所有可能排列的時間加總起來，除以n這個因數，相當於從輸入之中選擇一個隨機的排列。當我們這樣作，基準值本質上就是隨機的，導致這個演算法與亂數快速排序有一樣的執行時間。
更精確地說，對於輸入順序之所有排列情形的平均比較次數，可以藉由解出這個遞迴關係式可以精確地算出來。
在這裡，n-1 是分割所使用的比較次數。因為基準值是相當均勻地落在排列好的數列次序之任何地方，總和就是所有可能分割的平均。
這個意思是，平均上快速排序比理想的比較次數，也就是最好情況下，只大約比較糟39%。這意味著，它比最壞情況較接近最好情況。這個快速的平均執行時間，是快速排序比其他排序演算法有實際的優勢之另一個原因。
[编辑] 空間複雜度
被快速排序所使用的空間，依照使用的版本而定。使用原地（in-place）分割的快速排序版本，在任何遞迴呼叫前，僅會使用固定的額外空間。然而，如果需要產生O(log n)巢狀遞迴呼叫，它需要在他們每一個儲存一個固定數量的資訊。因為最好的情況最多需要O(log n)次的巢狀遞迴呼叫，所以它需要O(log n)的空間。最壞情況下需要O(n)次巢狀遞迴呼叫，因此需要O(n)的空間。
然而我們在這裡省略一些小的細節。如果我們考慮排序任意很長的數列，我們必須要記住我們的變數像是left和right，不再被認為是佔據固定的空間；也需要O(log n)對原來一個n項的數列作索引。因為我們在每一個堆疊框架中都有像這些的變數，實際上快速排序在最好跟平均的情況下，需要O(log2 n)空間的位元數，以及最壞情況下O(n log n)的空間。然而，這並不會太可怕，因為如果一個數列大部份都是不同的元素，那麼數列本身也會佔據O(n log n)的空間位元組。
非原地版本的快速排序，在它的任何遞迴呼叫前需要使用O(n)空間。在最好的情況下，它的空間仍然限制在O(n)，因為遞迴的每一階中，使用與上一次所使用最多空間的一半，且
它的最壞情況是很恐怖的，需要
空間，遠比數列本身還多。如果這些數列元素本身自己不是固定的大小，這個問題會變得更大；舉例來說，如果數列元素的大部份都是不同的，每一個將會需要大約O(log n)為原來儲存，導致最好情況是O(n log n)和最壞情況是O(n2 log n)的空間需求。
[编辑] 選擇的關連性
選擇算法（selection algorithm）可以選取一個數列的第k個最小值；一般而言這是比排序還簡單的問題。一個簡單但是有效率的選擇算法與快速排序的作法相當類似，除了對兩個子數列都作遞迴呼叫外，它僅僅針對包含想要的元素之子數列作單一的結尾遞迴（tail recursive）呼叫。這個小改變降低了平均複雜度到線性或是Θ(n)時間，且讓它成為一個原地算法。這個算法的一種變化版本，可已讓最壞情況下降為O(n)（參考選擇算法來得到更多資訊）。
相反地，一旦我們知道一個最壞情況的O(n)選擇算法是可以利用的，我們在快速排序的每一步可以用它來找到理想的基準（中位數），得到一種最化情況下O(n log n)執行時間的變化版本。在實際的實作，然而這種版本一般而言相當的慢。
[编辑] 實作範例
於此我們展示在數種語言下的幾個快速排序實作。我們在此僅秀出最普遍或獨特的一些；針對其他的實作，參見快速排序實作條目。
[编辑] C
void QuickSort(int data[], int left, int right) { int temp = data[left]; int p = left; int i = left, j = right; while (i <= j) { while (data[j] >= temp && j >= p ) j--; if(j >= p) { data[p] = data[j]; p = j; } while (data[i] <= temp && i <= p) i++; if (i <= p) { data[p] = data[i]; p = i; } } data[p] = temp; if(p-left > 1) QuickSort(data, left, p-1); if(right - p > 1) QuickSort(data, p+1, right); }
[编辑] C++
這是一個使用标准模版库（STL）的泛型式快速排序版本。
#include <functional> #include <algorithm> #include <iterator> template< typename BidirectionalIterator, typename Compare > void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) { if( first != last ) { BidirectionalIterator left = first; BidirectionalIterator right = last; BidirectionalIterator pivot = left++; while( left != right ) { if( cmp( *left, *pivot ) ) { ++left; } else { while( (left != right) && cmp( *pivot, *right ) ) right--; std::iter_swap( left, right ); } } if (cmp( *pivot, *left )) --left; std::iter_swap( first, left ); quick_sort( first, left, cmp ); quick_sort( right, last, cmp ); } } template< typename BidirectionalIterator > inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) { quick_sort( first, last, std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >() ); }
未使用STL的快速排序版本。
#include <iostream> int partition(int* array, int left, int right) { int index = left; int pivot = array[index]; swap(array[index], array[right]); for (int i=left; i<right; i++) { if (array[i] > pivot) // 降序 swap(array[index++], array[i]); } swap(array[right], array[index]); return index; } void qsort(int* array, int left, int right) { if (left >= right) return; int index = partition(array, left, right); qsort(array, left, index - 1); qsort(array, index + 1, right); }
[编辑] Java
import java.util.Comparator; import java.util.Random; public class Quicksort { public static final Random RND = new Random(); private static void swap(Object[] array, int i, int j) { Object tmp = array[i]; array[i] = array[j]; array[j] = tmp; } private static <E> int partition(E[] array, int begin, int end, Comparator<? super E> cmp) { int index = begin + RND.nextInt(end - begin + 1); E pivot = array[index]; swap(array, index, end); for (int i = index = begin; i < end; ++ i) { if (cmp.compare(array[i], pivot) <= 0) { swap(array, index++, i); } } swap(array, index, end); return (index); } private static <E> void qsort(E[] array, int begin, int end, Comparator<? super E> cmp) { if (end > begin) { int index = partition(array, begin, end, cmp); qsort(array, begin, index - 1, cmp); qsort(array, index + 1, end, cmp); } } public static <E> void sort(E[] array, Comparator<? super E> cmp) { qsort(array, 0, array.length - 1, cmp); } }
[编辑] Perl
sub qsort { return () unless @_; (qsort(grep { $_ < $_[0] } @_[1..$#_]), $_[0], qsort(grep { $_ >= $_[0] } @_[1..$#_])); }
[编辑] Python
def qsort(L): if not L: return [] return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + \ qsort([x for x in L[1:] if x>=L[0]])
[编辑] Joy
DEFINE sort == [small][]
[uncons [>] split]
[[swap] dip cons concat] binrec .
[编辑] PHP
function quicksort($seq) { if (count($seq) > 1) { $k = $seq[0]; $x = array(); $y = array(); for ($i=1; $i<count($seq); $i++) { if ($seq[$i] <= $k) { $x[] = $seq[$i]; } else { $y[] = $seq[$i]; } } $x = quicksort($x); $y = quicksort($y); return array_merge($x, array($k), $y); } else { return $seq; } }
[编辑] Haskell
sort :: (Ord a) => [a] -> [a] sort [] = [] sort (pivot:rest) = sort [y | y <- rest, y < pivot] ++ [pivot] ++ sort [y | y <- rest, y >=pivot]
[编辑] Prolog
split(H, [A|X], [A|Y], Z) :- order(A, H), split(H, X, Y, Z). split(H, [A|X], Y, [A|Z]) :- not(order(A, H)), split(H, X, Y, Z). split(_, [], [], []). quicksort([], X, X). quicksort([H|T], S, X) :- split(H, T, A, B), quicksort(A, S, [H|Y]), quicksort(B, Y, X).
[编辑] Ruby
def sort(array) # return [] if array.empty? return array if array.size < 2 left, right = array[1..-1].partition { |y| y <= array.first } sort(left) + [ array.first ] + sort(right) end
[编辑] SML
This example demonstrates the use of an arbitrary predicate in a functional language.
fun quicksort lt lst =
let val rec sort =
fn [] => []
| (x::xs) =>
let
val (left,right) = List.partition (fn y => lt (y, x)) xs
in sort left @ x :: sort right
end
in sort lst
end
[编辑] Pascal
program QSort; const Max = 1000; var Data: array[1..Max] of integer; I: Integer; procedure Sort(l, r: Integer); var i, j, x, y: integer; begin i := l; j := r; x := Data[(l+r) DIV 2]; while i<=j do begin while Data[i] < x do inc(i); while x < Data[j] do dec(j); if i <= j then begin y := Data[i]; Data[i] := Data[j]; Data[j] := y; inc(i); dec(j); end; end; if l < j then Sort(l, j); if i < r then Sort(i, r); end; begin {QSort} Randomize; for i := 1 to Max do Data[i] := Random(30000); Sort(1, Max); Writeln; for i := 1 to Max do Write(Data[i]:8); end.
[编辑] C#
public static void Sort(int[] numbers)
{
Sort(numbers, 0, numbers.Length - 1);
}
private static void Sort(int[] numbers, int left, int right)
{
if (left < right)
{
int middle = numbers[(left + right) / 2];
int i = left - 1;
int j = right + 1;
while (true)
{
while (numbers[++i] < middle) ;
while (numbers[--j] > middle) ;
if (i >= j)
break;
Swap(numbers, i, j);
}
Sort(numbers, left, i - 1);
Sort(numbers, j + 1, right);
}
}
private static void Swap(int[] numbers, int i, int j)
{
int number = numbers[i];
numbers[i] = numbers[j];
numbers[j] = number;
}
[编辑] VB.Net
Private m_i32ArrSort(10000) As Integer
Private Sub main()
m_vSorting(1, 10000)
End Sub
' Sort
Private Sub m_vSorting(ByVal i32Left As Integer, ByVal i32Right As Integer)
If (i32Left >= i32Right) Then Return
Dim i32I, i32J As Integer
Dim i32Middle = m_i32ArrSort(i32Left)
i32I = i32Left + 1
i32J = i32Right
Do
While (i32I <= i32Right)
If (m_i32ArrSort(i32I) > i32Middle) Then Exit While
i32I += 1
End While
While (i32J > i32Left)
If (m_i32ArrSort(i32J) < i32Middle) Then Exit While
i32J -= 1
End While
If (i32I > i32J) Then Exit Do
m_vSwap(i32I, i32J)
Loop
m_vSwap(i32Left, i32J)
m_vSorting(i32Left, i32J)
m_vSorting(i32J + 1, i32Right)
End Sub
' Swap
Private Sub m_vSwap(ByVal i32I As Integer, ByVal i32J As Integer)
Dim i32Tmp As Integer = m_i32ArrSort(i32I)
m_i32ArrSort(i32I) = m_i32ArrSort(i32J)
m_i32ArrSort(i32J) = i32Tmp
End Sub
外部連結
[编辑] 參考
- 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):847857, 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.
|
||||||||||||||||||||||||||||
