軟件 : 物理學類 > 快速排序
目錄
概述
　　快速排序(quick sort)是一種有效的排序算法。雖然算法在最壞的情況下運行時間為o(n^2)，但由於平均運行時間為o(nlogn)，並且在內存使用、程序實現復雜性上表現優秀，尤其是對快速排序算法進行隨機化的可能，使得快速排序在一般情況下是最實用的排序方法之一。
　　快速排序被認為是當前最優秀的內部排序方法。
實現
　　快速排序的實現基於分治法，具體分為三個步驟。假設待排序的序列為l[m..n]。
　　分解：序列l[m .. n]被劃分成兩個可能為空的子序列l[m .. pivot-1]和l[pivot+1 .. n]，使l[m .. pivot-1]的每個元素均小於或等於l[pivot]，同時l[pivot+1.. n]的每個元素均大於l[pivot]。其中l[pivot]稱為這一趟分割中的主元（也稱為樞軸、支點）。
　　解决：通過遞歸調用快速排序，對子序列l[m .. pivot-1]和l[pivot+1 .. r]排序。
　　合併：由於兩個子序列是就地排序的，所以對它們的合併不需要操作，整個序列l[m .. n]已排好序。
性質
　　內部排序
　　快速排序是一種內部排序方法。也就是說快速排序的排序對象是讀入內存的數據。
　　比較排序
　　快速排序確定元素位置的方法基於元素之間關鍵字大小的比較。
　　所有基於比較方法的排序方法的時間下界不會低於o(nlogn)。這個結論的具體證明，請參考有關算法的書籍，例如《算法導論》第8章。
　　快速排序在理想情況下，能嚴格地達到o(nlogn)的下界。一般情況下，快速排序與隨機化快速排序的平均情況性能都達到了o(nlogn)。
　　不穩定性
　　快速排序是一種不穩定的排序方法。簡單地說，元素a1, a2的關鍵字有a1.key=a2.key，則不穩定的排序方法不能保證a1, a2在排序後維持原來的位置先後關係。
　　原地排序
　　在排序的具體操作過程中，除去程序運行實現的空間消費（例如遞歸棧），快速排序算法衹需消耗確定數量的空間（即s(1)，常數級空間）。
　　這個性質的意義，在於在內存空間受到限製的係統（例如mcu）中，快速排序也能夠很好地工作。
時空復雜度
　　快速排序每次將待排序數組分為兩個部分，在理想狀況下，每一次都將待排序數組劃分成等長兩個部分，則需要logn次劃分。
　　而在最壞情況下，即數組已經有序或大致有序的情況下，每次劃分衹能減少一個元素，快速排序將不幸退化為冒泡排序，所以快速排序時間復雜度下界為o(nlogn)，最壞情況為o(n^2)。在實際應用中，快速排序的平均時間復雜度為o(nlogn)。
　　快速排序在對序列的操作過程中衹需花費常數級的空間。空間復雜度s(1)。
　　但需要註意遞歸棧上需要花費最少logn 最多n的空間。
隨機化算法
　　快速排序的最壞情況基於每次劃分對主元的選擇。基本的快速排序選取第一個元素作為主元。這樣在數組已經有序的情況下，每次劃分將得到最壞的結果。一種比較常見的優化方法是隨機化算法，即隨機選取一個元素作為主元。這種情況下雖然最壞情況仍然是o(n^2)，但最壞情況不再依賴於輸入數據，而是由於隨機函數取值不佳。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機化快速排序可以對於絶大多數輸入數據達到o(nlogn)的期望時間復雜度。一位前輩做出了一個精闢的總結：“隨機化快速排序可以滿足一個人一輩子的人品需求。”
　　隨機化快速排序的唯一缺點在於，一旦輸入數據中有很多的相同數據，隨機化的效果將直接減弱。對於極限情況，即對於n個相同的數排序，隨機化快速排序的時間復雜度將毫無疑問的降低到o(n^2)。
減少遞歸棧使用的優化
　　快速排序的實現需要消耗遞歸棧的空間，而大多數情況下都會通過使用係統遞歸棧來完成遞歸求解。在元素數量較大時，對係統棧的頻繁存取會影響到排序的效率。
　　一種常見的辦法是設置一個閾值，在每次遞歸求解中，如果元素總數不足這個閾值，則放棄快速排序，調用一個簡單的排序過程完成該子序列的排序。這樣的方法減少了對係統遞歸棧的頻繁存取，節省了時間的消費。
　　一般的經驗表明，閾值取一個較小的值，排序算法采用選擇、插入等緊湊、簡潔的排序。一個可以參考的具體方案：閾值t=10，排序算法用選擇排序。
　　閾值不要太大，否則省下的存取係統棧的時間，將會被簡單排序算法較多的時間花費所抵消。
　　另一個可以參考的方法，是自行建棧模擬遞歸過程。但實際經驗表明，收效明顯不如設置閾值。
c++例程
　　以下是一個用c++編寫的快速排序程序。雖然c標準庫中提供了快速排序，但作為快速排序的介紹，原理程序的代碼更加有助於對快速排序運行過程的分析。
　　在這個例程中，對於數組x[]的0~n-1號元素的排序，初始調用為：quicksort(x, 0, n-1);
　　int quicksort_partition(int l[], int lbb, int ubb)
　　{
　　//隨機化
　　int irndpivid;
　　srand(unsigned(time(0)));
　　irndpivid = (rand() % (ubb - lbb + 1)) + lbb;
　　swap(l[irndpivid], l[ubb]);
　　//快排
　　int ipivvalue;
　　int i;
　　int ipivpos;
　　ipivvalue = l[ubb];
　　ipivpos = lbb - 1;
　　for (i=lbb; i<=ubb-1; i++)
　　{
　　if (l[ i ] <= ipivvalue)
　　{
　　ipivpos++;
　　swap(l[ipivpos], l[ i ]);
　　}
　　}
　　ipivpos++;
　　swap(l[ipivpos], l[ubb]);
　　return ipivpos;
　　}
　　void quicksort(int l[], int lbb, int ubb)
　　{
　　int ipiv;
　　if (lbb < ubb)
　　{
　　ipiv = quicksort_partition(l, lbb, ubb);
　　quicksort(l, lbb, ipiv - 1);
　　quicksort(l, ipiv + 1, ubb);
　　}
　　return;
　　}
使用c++標準庫的快速排序函數
　　c++的標準庫stdlib.h中提供了快速排序函數。
　　請在使用前加入對stdlib.h的引用：#include <cstdlib> 或 #include <stdlib.h>
　　qsort(void* base, size_t num, size_t width, int(*)compare(const void* elem1, const void* elem2))
　　參數表
　　*base: 待排序的元素（數組，下標0起）。
　　num: 元素的數量。
　　width: 每個元素的內存空間大小（以字節為單位）。可用sizeof()測得。
　　int(*)compare: 指嚮一個比較函數。*elem1 *elem2: 指嚮待比較的數據。
　　比較函數的返回值
　　返回值是int類型，確定elem1與elem2的相對位置。
　　elem1在elem2右側返回正數，elem1在elem2左側返回負數。
　　控製返回值可以確定升序/降序。
　　一個升序排序的例程：
　　int compare(const void *elem1, const void *elem2)
　　{
　　return *((int *)(elem1)) - *((int *)(elem2));
　　}
　　int main()
　　{
　　int a[100];
　　qsort(a, 100, sizeof(int), compare);
　　return 0;
　　}
pascal例程
　　這個例程中假設待排序的數組是全局變量a[]。
　　procedure qsort(s,t:longint);
　　var
　　i,j,x,temp:longint;
　　begin
　　i:=s;j:=t;x:=a[(i+j)div 2];
　　repeat
　　while a[ i ]<x do inc(i); {找左邊比他大的}
　　while a[j]>x do dec(j);{找右邊比他小的}
　　if i<=j then{交換}
　　begin
　　temp:=a[ i ];a[ i ]:=a[j];a[j]:=temp;
　　inc(i);dec(j);
　　end;
　　until i>j;
　　if s<j then qsort(s,j);
　　if i<t then qsort(i,t);
　　end;
包含詞
快速排序算法快速排序程序段