相信學過數據結構與算法的朋友對于快速排序應該并不陌生，本文就以實例講述了C++快速排序的分析與優化，對于C++算法的設計有很好的借鑒價值。具體分析如下：
一、快速排序的介紹
快速排序是一種排序算法，對包含n個數的輸入數組，最壞的情況運行時間為Θ(n2)[Θ 讀作theta]。雖然這個最壞情況的運行時間比較差，但快速排序通常是用于排序的最佳的實用選擇。這是因為其平均情況下的性能相當好：期望的運行時間為 Θ(nlgn)，且Θ(nlgn)記號中隱含的常數因子很小。另外，它還能夠進行就地排序，在虛擬內存環境中也能很好的工作。
和歸并排序一樣，快速排序也是基于分治法（Divide and conquer）：
分解：數組A[p..r]被劃分成兩個(可能為空)的子數組A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每個元素都小于等于A[q]，A[q+1..r]中的每個元素都大于等于A[q]。這樣元素A[q]就位于其最終位置上了。
解決：通過遞歸調用快速排序，對子數組A[p..q-1]和A[q+1..r]排序。
合并：因為兩個子數組是就地排序，不需要合并，整個數組已有序。
偽代碼如下：
PARTITION(A, p, r) x = A[p] i = p for j=p+1 to r do if A[j] <= x then i = i+1 exchange(A[i],A[j]) exchange(A[p], A[i]) return i QUICKSORT(A, p, r) if p < r then q = PARTITION(A, p, r) QUICKSORT(A, p, q-1) QUICKSORT(A, q+1, r)
二、性能分析
1、最壞情況
快速排序的最壞情況發生在當數組已經有序或者逆序排好的情況下。這樣的話劃分過程產生的兩個區域中有一個沒有元素，另一個包含n-1個元素。此時算法的運行時間可以遞歸地表示為：T(n) = T(n-1)+T(0)+Θ(n)，遞歸式的解為T(n)=Θ(n^2)?？梢钥闯?，快速排序算法最壞情況運行時間并不比插入排序的更好。
2、最好情況
如果我們足夠幸運，在每次劃分操作中做到最平衡的劃分，即將數組劃分為n/2:n/2。此時得到的遞歸式為T(n) = 2T(n/2)+Θ(n)，根據主定理的情況二可得T(n)=Θ(nlgn)。
3、平均情況
假設一：快排中的劃分點非常偏斜，比如每次都將數組劃分為1/10 : 9/10的兩個子區域，這種情況下運行時間是多少呢？運行時間遞歸式為T(n) = T(n/10)+T(9n/10)+Θ(n)，使用遞歸樹解得T(n)=Θ(nlgn)?？梢钥闯?，當劃分點非常偏斜的時候，運行時間仍然是Θ(nlgn)。
假設二：Partition所產生的劃分既有“好的”，也有“差的”，它們交替出現。這種平均情況下運行時間又是多少呢？這時的遞歸式為（G表示Good，B表示Bad）：
G(n) = 2B(n/2) + Θ(n)
B(n) = G(n-1) + Θ(n)
解：G(n) = 2(G(n/2-1) + Θ(n/2)) + Θ(n) = 2G(n/2-1) + Θ(n) = Θ(nlgn)
可以看出，當好、差劃分交替出現時，快排的運行時間就如全是好的劃分一樣，仍然是Θ(nlgn) 。
三、快排的優化
經過上面的分析可以知道，在輸入有序或逆序時快速排序很慢，在其余情況則表現良好。如果輸入本身已被排序，那么就糟了。那么我們如何確保對于所有輸 入，它均能夠獲得較好的平均情況性能呢？前面的快速排序我們默認使用數組中第一個元素作為主元。假設隨機選擇數組中的元素作為主元，則快排的運行時間將不 依賴于輸入序列的順序。我們把隨機選擇主元的快速排序叫做Randomized Quicksort。
在隨機化的快速排序中，我們不是始終選擇第一個元素作為主元，而是從數組A[p…r]中隨機選擇一個元素，然后將其與第一個元素交換。由于主元元素是隨機選擇的，我們期望在平均情況下，對輸入數組的劃分能夠比較對稱。
偽代碼如下：
RANDOMIZED-PARTITION(A, p, r) i = RANDOM(p, r) exchange(A[p], A[i]) return PARTITION(A, p, r) RANDOMIZED-QUICKSORT(A, p, r) if p < r then q = RANDOMIZED-PARTITION(A, p, r) RANDOMIZED-QUICKSORT(A, p, q-1) RANDOMIZED-QUICKSORT(A, q+1, r)
我們對3萬個元素的有序序列分別進行傳統的快速排序 和 隨機化的快速排序，并比較它們的運行時間：
/************************************************************************* > File Name: QuickSort.cpp > Author: SongLee ************************************************************************/ #include<iostream> #include<cstdlib> // srand rand #include<ctime> // clock_t clock using namespace std; void swap(int &a, int &b) { int tmp = a; a = b; b = tmp; } // 傳統劃分操作 int Partition(int A[], int low, int high) { int pivot = A[low]; int i = low; for(int j=low+1; j<=high; ++j) { if(A[j] <= pivot) { ++i; swap(A[i], A[j]); } } swap(A[i], A[low]); return i; } // 隨機化劃分操作，隨機選擇pivot int Partition_Random(int A[], int low, int high) { srand(time(NULL)); int i = rand() % (high+1); swap(A[low], A[i]); return Partition(A, low, high); } // 傳統快排 void QuickSort(int A[], int low, int high) { if(low < high) { int pos = Partition(A, low, high); QuickSort(A, low, pos-1); QuickSort(A, pos+1, high); } } // 隨機化快速排序 void QuickSort_Random(int A[], int low, int high) { if(low < high) { int pos = Partition_Random(A, low, high); QuickSort_Random(A, low, pos-1); QuickSort_Random(A, pos+1, high); } } int main() { clock_t t1, t2; // 初始化數組 int A[30000]; for(int i=0; i<30000; ++i) A[i] = i+1; t1 = clock(); QuickSort(A, 0, 30000-1); t1 = clock() - t1; cout << "Traditional quicksort took "<< t1 << " clicks(about " << ((float)t1)/CLOCKS_PER_SEC << " seconds)." << endl; t2 = clock(); QuickSort_Random(A, 0, 30000-1); t2 = clock() - t2; cout << "Randomized quicksort took "<< t2 << " clicks(about " << ((float)t2)/CLOCKS_PER_SEC << " seconds)." << endl; return 0; }運行結果如下：
[songlee@localhost ~]$ ./QuickSort Traditional quicksort took 1210309 clicks(about 1.21031 seconds). Randomized quicksort took 457573 clicks(about 0.457573 seconds). [songlee@localhost ~]$ ./QuickSort Traditional quicksort took 1208038 clicks(about 1.20804 seconds). Randomized quicksort took 644950 clicks(about 0.64495 seconds).
從運行結果可以看出，對于有序的輸入，隨機化版本的快速排序的效率會高很多。
問題記錄：
我們知道交換兩個變量的值有以下三種方法：
int tmp = a; // 方法一 a = b; b = tmp a = a+b; // 方法二 b = a-b; a = a-b; a = a^b; // 方法三 b = a^b; a = a^b;
但是你會發現在本程序中，如果swap函數使用后面兩種方法會出錯。由于方法二和方法三沒有使用中間變量，它們交換值的原理是直接對變量的內存單元進行操作。如果兩個變量對應的同一內存單元，則經過兩次加減或異或操作，內存單元的值已經變為了0，因而不能實現變量值交換。所以當需要交換值的變量可能是同一變量時，必須使用第三變量實現交換，否則會對變量清零。
新聞熱點
疑難解答
圖片精選
