# 快速排序的基本思想 ????????? 快速排序算法是一種不穩定的排序算法。其時間復雜度為O(nlogn)，最壞復雜度為O(n^2)；快排的平均空間復雜度為O(logn)，關于空間界的論斷來自于《編程珠璣第2版》第113頁。但是其最壞空間復雜度為O(n)。 ????? 快速排序的基本思想是使用兩個指針來遍歷待排序的數組，**根據兩個指針遍歷的方向可以分為兩類：第一，兩個指針從待排序數組的同一個方向遍歷。第二，兩個指針分別從帶排序數組的兩端進行遍歷。下列的幾種算法都可以歸為這兩類中的某類。 ?????? 下圖給出的是兩個指針從同一方向遍歷時的狀態。下圖的第一個圖給出的是循環過程中的狀態，在循環中，low指向的是小于樞紐的那部分元素的最右端，high在未排序的部分遍歷。循環直到high指針到達right的位置（數組的最右端），如下圖第二個圖所示。此時數組除了樞紐pivot被劃分為兩部分：小于pivot的和大于等于pivot的。然后將low和樞紐元素交換就可以得到本次排序的第一趟結果，如下圖的第三幅圖所示。  ???????? ????????? 當**從兩個方向分別遍歷數組時**，下圖是遍歷的循環過程狀態。循環時，low向右移動，high向左移動。  # Hoare的變形版本(空穴法) 假設待排序的數組為a[]，快速排序算法最常見的做法是將第一個元素設置為樞紐元。設置兩個指針low和high，它們分別指向待排序的數組的低和高位： （1）high向左移動找小于樞紐的元素，找到后（找到的是a[high]）將其值存儲在a[low]中，那么此時high所指的元素其實沒有意義了，因為a[high]已經存儲到了a[low]中，那么可以認為high所指的是空穴，該空穴將存儲（2）中low指針找到的大于樞紐的元素。 （2）然后low向右移動找大于樞紐元的元素，找到后（a[low]）將其存儲在a[high]中（high指的是空穴），同樣的，此時a[low]存的數沒有意義了，因為該數已經存到了a[high]中，那么low所指的是空穴，該空穴存儲下次high找到的小于樞紐的數。 （3）當兩個指針相遇時，上述循環終止，此時low指向空穴，將樞紐存入空穴。這就是一次遞歸過程。遞歸該過程。 例如，對數組5 1 9 3 8 4 7進行排序，給出一次遞歸的過程：  第1步：low指向5，high指向7。選取第一個元素5為樞紐pivot，則可以認為第一個元素處是空穴，即low指向空穴。 第2步：high向左移動，找到了小于樞紐5的元素4，將這個元素存儲到low所指的空穴中，此時，high所指的位置成了空穴。 第3步：low向右移動，找到了大于樞紐5的元素9，將這個元素存儲到high所指的空穴中，此時，low所指的位置成了空穴。 第4步：重復第2步，high找到的小元素3存到了low所指的空穴中，high所指位置成為空穴。 第5步：low指針此時仍小于high，所以low向右移動一次，此時vec[low]等于樞紐，low == high，那么內層第二個while循環將不再執行第二次。此時，low和high都指向空穴。外層while循環終止，將樞紐元素放入low所指的空穴。可以看到，**該算法**一趟排序后樞紐被放在了最終的位置上**（這里的樞紐為5）。 ### 遞歸算法 **注意**：該算法的內層while循環的判斷條件如果沒有等于號的話，遇到等于樞紐的元素會死循環，和[這個算法的實現](http://blog.csdn.net/cnm_1314/article/details/25894813)對比下。 如下是該思想的代碼： ~~~ //快速排序版本一，vec[0]為樞紐 template<typename T> int PartionQuickSort1(vector<T> &vec, int left, int right) { ?T pivot = vec[left];//設置樞紐 ?int low = left; ?int high = right; ?while (low < high) {//注意兩個內層while的順序不能換 ??? ?while (low < high && vec[high] >= pivot) //這里是>=不能使>，否則當數組元素等于樞紐時會死循環 ??? ??? ?high--; ??? ?vec[low] = vec[high];//將找到的小于于樞紐的元素存到high所指的空穴 ??? ?while (low < high && vec[low] <= pivot) //這里是<=不能使<，否則當數組元素等于樞紐時會死循環 ??? ??? ?low++; ??? ?vec[high] = vec[low];//將找到的大于樞紐的元素存到high所指的空穴 ?} ?vec[low] = pivot; ?return low;? //返回樞紐的位置 } template<typename T> void QuickSort1(vector<T> &vec, int left, int right) { ?if (left < right) { ??? ?int partion = PartionQuickSort1(vec, left, right); ??? ?QuickSort1(vec, left, partion - 1); ??? ?QuickSort1(vec, partion + 1, right); ?} } /* 該算法需要注意的是在PartionQuickSort1函數中兩個內層while的順序不能交換，否則會覆蓋元素。如果兩個內層while循環交換， 例如在上邊的演示中，首先low指針右移，找到9，則要將a[low] = 9 存入a[high] = 7的位置，這樣7還沒被保存，那么該值就丟失了。 算法中之所以可以在循環中賦值是因為樞紐元素值已經保存在了pivot中。 */ //如果將待排序數組的最右側元素設為樞紐，那么則內層while循環需要交換，如下程序： template<typename T> int PartionQuickSort12(vector<T> &vec, int left, int right) { ?T pivot = vec[right]; //設置最右側元素為樞紐 ?int low = left; ?int high = right; ?while (low < high) { //注意下面內層while的順序 ??? ?while (low < high && vec[low] <= pivot) ??? ??? ?low++; ??? ?vec[high] = vec[low]; ??? ?while (low < high && vec[high] >= pivot) ??? ??? ?high--; ??? ?vec[low] = vec[high]; ?} ?vec[low] = pivot; ?return low; } template<typename T> void QuickSort12(vector<T> &vec, int left, int right) { ?if (left < right) { ??? ?int partion = PartionQuickSort1(vec, left, right); ??? ?QuickSort12(vec, left, partion - 1); ??? ?QuickSort12(vec, partion + 1, right); ?} } ~~~ ### 非遞歸算法 以左側元素為樞紐，非遞歸算法：利用STL棧適配器stack ~~~ //快速排序的非遞歸算法，以第一個元素為樞紐 //非遞歸算法用一個stack輔助數據結構，棧存放下一次要排序的兩個下標 template<typename T> void QuickSort1NoRecursion(vector<T>& vec, int left, int right) { stack<int> st; //注意每次入棧都將較大的下標先入棧，那么 //每次出棧相反：較大的小標會后出棧 st.push(right); st.push(left); int maxsize = 0; while (!st.empty()) { if (st.size() > maxsize) maxsize = st.size(); int low = st.top(); st.pop(); int high = st.top(); st.pop(); //cout << low << " " << high << endl; int mid = PartionQuickSort1(vec, low, high); if (mid - 1 > low) { st.push(mid - 1); st.push(low); } if (mid + 1 < high) { st.push(high); st.push(mid + 1); } } //cout << "max stack size: " << maxsize << endl; return; } ~~~ # Hoare版本（直接交換元素） 這里給出Hoare提出的快速排序算法，其思想與上述的類似，也是兩個指針low和high分別指向待排序數組的低位和高位，然后low向右遍歷找大于樞紐的、high向左遍歷找小于樞紐的，只是這里是當找到了就將a[low]和a[high]交換，而不是產生空穴。 代碼如下： ~~~ //快速排序版本二 template<typename T> void SwapQuickSort(T &a, T &b) { ?T temp = a; ?a = b; ?b = temp; } template<typename T> int PartionQuickSort2(vector<T> &vec, int left, int right) { ?T pivot = vec[left]; ?int low = left - 1; ?int high = right? + 1; ?for (; ;) { ??? ?do { ??? ??? ?high--; ??? ?}while (vec[high] > pivot); //這里沒有等于，見“對比版本二和版本三”的下邊分析 ? ??? ? do { ??? ??? ?low++; ??? ?}while (vec[low] < pivot); //這里沒有等于，見“對比版本二和版本三”的下邊分析 ??? ?/*這里的循環是錯誤的，當某元素等于pivot時會死循環 ??? ?while (vec[high] > pivot) ??? ??? ?high--; ??? ?while (vec[low] < pivot) ??? ??? ?low++; ??? ?*/ ??? ?if (low < high) ??? ??? ?SwapQuickSort(vec[low], vec[high]); ??? ?else ??? ??? ?return high; ?} } template<typename T> void QuickSort2(vector<T> &vec, int left, int right) { ?if (left < right) { ??? ?int partion = PartionQuickSort2(vec, left, right); ??? ?QuickSort2(vec, left, partion); ??? ?/* ??? ?注意上一行與版本一不同，不是QuickSort2(vec, left, partion - 1) ??? ?因為版本一中每次排序后會將樞紐pivot放在最終的位置上，但是該算法 ??? ?只保證每次排序后樞紐位于待排序數組的有半部分，不保證pivot在最終 ??? ?的位置上，因此要將Partion所指的位置加入下一次排序 ??? ?*/ ??? ?QuickSort2(vec, partion + 1, right); ?} } ~~~ 例如，對數組5 1 9 3 8 4 7進行排序，第一次排序的過程：  初始狀態：low指向數組前一個位置，high指向數組后一個位置。樞紐為第一個元素5。 第1步：high向左移動，找到**不大于樞紐**的元素4，停止；low向右移動，找到**不小于樞紐**的元素5，停止；此時low < high所以將它們指向的元素交換。結果如（1）圖所示。 第2步：重復第1步，high在3所在位置停下，low在9所在位置停下；此時low < high所以將它們指向的元素交換。結果如（2）圖所示。 第3步：由于for循環是無條件循環的，因此與版本一不同的是，這里low 會越過high，如（3）圖所示；high指向3，low指向9。此時if檢測到low不小于high了，則返回high，一次排序結束。 繼續給出第二趟排序時，左側數組元素的排序過程：  可以看出，**Hoare排序，每次排序結束后并不保證樞紐在最終的位置上，只保證樞紐位于數組的右半部分**，因此Partion所指的位置要進行下一次排序。 # 算法導論上方法：單向劃分 **該算法與上邊算法最大的不同是**：該算法的low和high元素都是從數組開始向后移動，而不是一前一后，且將樞紐設置為最右端的元素。在排序中，**low指向已經排序的、小于樞紐的元素的最右位置（那么low的右側下一個位置就是大于樞紐的了）**，high指向待排序的數組，當high找到了一個小于等于樞紐的位置，則將low加1（此時low指向了大于樞紐的第一個位置），然后將low和high所指的位置元素交換；交換后low所指的元素小于樞紐（此時，low的右側下一個位置就是大于樞紐的了），high所指的值大于樞紐，high繼續循環。  初始狀態：low指向數組前一個位置，high指向數組第一個位置，樞紐為最右位置。 第1步：high所指的5小于樞紐7，所以low++，此時high也指向的是5，所以5和5交換，數組不變，如（1）圖所示。 第2步：high向右移動到1，1小于樞紐5，所以low++，此時high也指向1，所以1和1交換，數組不變，若（2）圖所示。 第3步：high繼續右移到3的位置，此時3小于樞紐，所以low++，將low和high所指位置的元素交換，結果如圖（3）所示。 第4步：high繼續向右移動到4的位置，4小于樞紐，所以low++，將low和high所指位置的元素交換，結果如圖（4）所示。 第5步：high在第4步中++后指向了數組最右側，此時for循環不會再執行，接著執行SwapQuickSort(vec[low + 1], vec[right])，**交換low+1和樞紐元素**，結果如圖（5）所示。 **可以看出在每次交換后，low所指的都是已經遍歷的、小于樞紐的一系列元素的最右邊一個（low的右邊下一個元素就大于樞紐了），因此high發現了小于等于樞紐的元素后，交換low和high所指元素，即可將low所指的大元素放到數組右側，而把high所指的小元素放到數組左側。該算法和版本一一樣，每次排序后都將樞紐元素放在了最終的位置上**。 代碼如下： ~~~ //快速排版本三，算法導論上的方法 template<typename T> void SwapQuickSort(T &a, T &b) { T temp = a; a = b; b = temp; } template<typename T> int PartionQuickSort3(vector<T> &vec, int left, int right) { int low = left - 1; int high; T pivot = vec[right]; for (high = left; high < right; high++) { if (vec[high] <= pivot) { //將找到的小于樞紐的元素移到左邊 low++;//low++后low指向了數組第一個大于樞紐的位置 //將low所指的、第一個大于樞紐的元素與high所指的小于樞紐的元素交換 SwapQuickSort(vec[low], vec[high]); } } SwapQuickSort(vec[low + 1], vec[right]); return low + 1; } template<typename T> void QuickSort3(vector<T>& vec, int left, int right) { if (left < right) { int partion = PartionQuickSort3(vec, left, right); QuickSort3(vec, left, partion - 1); QuickSort3(vec, partion + 1, right); } } ~~~ 這里給出《編程珠璣第2版》第112頁的實現方法，與版本三類似，只是這里用的是最左側的為樞紐元。 ~~~ template<typename T> void QuickSort32(vector<T>& vec, int left, int right) { if (right <= left) return; int low = left; int high; for (high = left + 1; high <= right; high++) { if (vec[high] < vec[left]) SwapQuickSort(vec[++low], vec[high]); } SwapQuickSort(vec[left], vec[low]); QuickSort32(vec, left, low - 1); QuickSort32(vec, low + 1, right); } ~~~ # 對比版本二和版本三 ?????? 這里的分析思路來源于《編程珠璣》。 **（1）待排序的數都相等** 版本三給出的兩個指針單向遍歷的方法，對于一般待排序序列效果較好，但是**如果n個數是相等的話**，那么版本三的方法將很糟糕，n-1劃分中，每次都需要O(n)才能排序一個元素，總運行時間為O(n^2)；而如果使用[插入排序](http://blog.csdn.net/u013074465/article/details/42043665)，則每次不需要移動元素，總時間為O(n)。而版本二對于相同的待排序序列則可以避免這個問題。 **（2）如何處理等于樞紐的元素** 注意到版本二中內層的do-while循環，判斷條件中沒有“等于”，也就是說，對于等于樞紐的元素我們的處理是：遇到等于樞紐的元素時，**停止掃描**，交換low和high所指的元素。這樣做增加了交換的次數，但是這樣就將等于樞紐的元素交換到了數組的中間，可以將數組劃分為幾乎相等的兩個數組，總的時間為O(nlogn)。**試想，如果遇到等于樞紐元不停止的話**，對于**所有元素都相等的**待排序數組，首先high執行do-while循環，直到待排序數組的最左側與low相遇，此時一趟排序后返回的high（即下一趟排序的遞歸分界線）很靠近數組左側，這樣的話，將數組分成了及其不均等的兩部分（左側部分僅為1個元素），那么相當于下趟排序是對n-1個相等元素進行，再下趟排序對相等的n-2個元素進行，這樣的話和上邊（1）中提到的一樣，總時間仍為O(n^2)。而且，如果不停止，還要有相應的程序防止low和high越界。 ?????? 因此，進行不必要的交換建立兩個均等的子數組比蠻干冒險得到不均衡的子數組好。所以，遇到等于樞紐的元素，要讓low和high停下來，交換它們。 **（3）如果數組排序前已經有序** 如果數組排序前已經遞增有序，這時，如果以第一個（最小）元素為樞紐的話，劃分的仍然是及其不均衡的子數組，總時間仍為O(n^2)。而此時，[插入排序](http://blog.csdn.net/u013074465/article/details/42043665)，則每次不需要移動元素，總時間為O(n)。因此，固定選擇某個元素為樞紐存在不科學的情況，于是有了下面的隨機樞紐排序方法。 # 隨機樞紐的快速排序 以上的方法都是固定某個位置為樞紐，該方法是隨機選取一個位置為樞紐。 思想為：**首先產生隨機的樞紐位置i，然后交換i、right或者交換i、left。那么接下來就可以繼續使用上述的方法了。**下面使用版本一的方法。 代碼： ~~~ //版本四,隨機的樞紐，使用版本一的方法 int Rand(int left, int right) { //產生數組范圍內的隨機下標 int size = right - left + 1; return left + rand() % size; } template<typename T> int PartionQuickSort4(vector<T> &vec, int left, int right) { SwapQuickSort(vec[Rand(left, right)], vec[right]);//將隨機的樞紐交換到right位置處 T pivot = vec[right]; //設置樞紐 int low = left; int high = right; while (low < high) {//注意兩個內層while的順序不能換 while (low < high && vec[low] <= pivot) low++; vec[high] = vec[low]; while (low < high && vec[high] >= pivot) high--; vec[low] = vec[high]; } vec[low] = pivot; return low; } template<typename T> void QuickSort4(vector<T> &vec, int left, int right) { if (left < right) { int partion = PartionQuickSort1(vec, left, right); QuickSort4(vec, left, partion - 1); QuickSort4(vec, partion + 1, right); } } ~~~ # 樞紐三數中值法 **上述的程序均使用了大量的時間排序很小的數組，效率不高，如果利用[插入排序](http://blog.csdn.net/u013074465/article/details/42043665)等算法來排序很小的子數組，效率會提高很多**，該算法就是這么做的。而且，該算法是選取三個數的中間值作為樞紐元，只給出代碼，具體分析見《數據結構與算法分析C++描述第3版》。 ~~~ //版本五，取中間值為樞紐 template <typename T> const T & median( vector<T> & a, int left, int right ) { int center = ( left + right ) / 2; if( a[ center ] < a[ left ] ) swap( a[ left ], a[ center ] ); if( a[ right ] < a[ left ] ) swap( a[ left ], a[ right ] ); if( a[ right ] < a[ center ] ) swap( a[ center ], a[ right ] ); swap( a[ center ], a[ right - 1 ] ); return a[ right - 1 ]; } template <typename T> void QuickSort5( vector<T> & a, int left, int right ) { if (left + 10 <= right) { T pivot = median( a, left, right ); int i = left, j = right - 1; for( ; ; ) { while( a[ ++i ] < pivot ) { } while( pivot < a[ --j ] ) { } if( i < j ) swap( a[ i ], a[ j ] ); else break; } swap( a[ i ], a[ right - 1 ] ); QuickSort5( a, left, i - 1 ); QuickSort5( a, i + 1, right ); } else { //使用插入排序來處理很小的數組(n < 10)提高效率 InsertionSortQuickSort(a, left, right); } } template <typename T> void InsertionSortQuickSort( vector<T> & a, int left, int right ) { for( int p = left + 1; p <= right; p++ ) { T tmp = a[ p ]; int j; for( j = p; j > left && tmp < a[ j - 1 ]; j-- ) a[ j ] = a[ j - 1 ]; a[ j ] = tmp; } } ~~~ # 各個算法版本的性能測試分析 測試環境： VS2010旗艦版。Intel i3處理器（2.94Ghz），2.93G內存，32位操作系統。 ### 一、隨機產生的十個數 對以上前四個算法、三種版本有效性測試： ~~~ int main() { int max = 10; int i = 0; vector<int> ivec1, ivec12, ivec2, ivec3; srand((unsigned int)time(0)); while (i < max) { i++; int value = rand(); ivec1.push_back(value); ivec12.push_back(value); ivec2.push_back(value); ivec3.push_back(value); } cout << "unorder: " << endl; PrintValue(ivec1); cout << "ordered: " << endl; QuickSort1(ivec1, 0, ivec1.size() - 1); PrintValue(ivec1); QuickSort12(ivec12, 0, ivec12.size() - 1); PrintValue(ivec12); QuickSort2(ivec2, 0, ivec2.size() - 1); PrintValue(ivec2); QuickSort3(ivec3, 0, ivec3.size() - 1); PrintValue(ivec3); } ~~~  ### 二、大量隨機數測試 ### （1）某次隨機產生的10,000,000（一千萬）個數測試 輸出各個算法用時(ms)： ~~~ int main() { int max = 10000000; int i = 0; vector<int> ivec1, ivec12, ivec2, ivec3, ivec4, ivec5; srand((unsigned int)time(0)); while (i < max) { i++; int value = rand(); ivec1.push_back(value); ivec12.push_back(value); ivec2.push_back(value); ivec3.push_back(value); ivec4.push_back(value); ivec5.push_back(value); } clock_t time1 = clock(); QuickSort1(ivec1, 0, ivec1.size() - 1); clock_t time2 = clock(); cout << "版本一（以最左側元素為樞紐）:" << time2 - time1 << endl; QuickSort12(ivec12, 0, ivec12.size() - 1); clock_t time3 = clock(); cout << "版本一（以最右側元素為樞紐）:" << time3 - time2 << endl; QuickSort2(ivec2, 0, ivec2.size() - 1); clock_t time4 = clock(); cout << "版本二:" << time4 - time3 << endl; QuickSort3(ivec3, 0, ivec3.size() - 1); clock_t time5 = clock(); cout << "版本三:" << time5 - time4 << endl; QuickSort4(ivec4, 0, ivec4.size() - 1); clock_t time6 = clock(); cout << "版本四:" << time6 - time5 << endl; QuickSort5(ivec5, 0, ivec5.size() - 1); clock_t time7 = clock(); cout << "版本五:" << time7 - time6 << endl; } ~~~  ### （2）隨機產生一百萬個數，連續測試10次 如下圖所示：每一行依次是某個算法10次測試所有時間，最后一列為各個算法耗時的平均值。 ~~~ //vec_time用于記錄所有算法的十次耗時 //每個元素表示一種算法 vector< vector<int> > vec_time(10); //進行十次測試 for (int a = 0; a < 10; ++a) { int max = 1000000; //每次測試的都是隨機的一百萬個數 int i = 0; vector<int> ivec1, ivec1_none, ivec12, ivec2, ivec3, ivec4, ivec5; srand((unsigned int)time(0)); while (i < max) { i++; int value = rand(); ivec1.push_back(value); ivec1_none.push_back(value); ivec12.push_back(value); ivec2.push_back(value); ivec3.push_back(value); ivec4.push_back(value); ivec5.push_back(value); } clock_t time1 = clock(); QuickSort1(ivec1, 0, ivec1.size() - 1); clock_t time2 = clock(); //cout << "版本一（左側樞紐）:" << time2 - time1 << endl; vec_time[0].push_back(time2 - time1); clock_t time_none1 = clock(); QuickSort1NoRecursion(ivec1_none, 0, ivec1_none.size() - 1); clock_t time_none2 = clock(); //cout << "版本一（非遞歸法）:" << time_none2 - time_none1 << endl; //PrintValue(ivec1_none); vec_time[1].push_back(time_none2 - time_none1); clock_t time31 = clock(); QuickSort12(ivec12, 0, ivec12.size() - 1); clock_t time3 = clock(); //cout << "版本一（右側樞紐）:" << time3 - time31 << endl; vec_time[2].push_back(time3 - time31); clock_t time41 = clock(); QuickSort2(ivec2, 0, ivec2.size() - 1); clock_t time4 = clock(); //cout << "版本二（直接交換）:" << time4 - time41 << endl; vec_time[3].push_back(time4 - time41); clock_t time51 = clock(); QuickSort3(ivec3, 0, ivec3.size() - 1); clock_t time5 = clock(); //cout << "版本三（單向劃分）:" << time5 - time51 << endl; vec_time[4].push_back(time5 - time51); clock_t time61 = clock(); QuickSort4(ivec4, 0, ivec4.size() - 1); clock_t time6 = clock(); //cout << "版本四（隨機樞紐）:" << time6 - time61 << endl; vec_time[5].push_back(time6 - time61); clock_t time71 = clock(); QuickSort5(ivec5, 0, ivec5.size() - 1); clock_t time7 = clock(); //cout << "版本五（三數取中）:" << time7 - time71 << endl; vec_time[6].push_back(time7 - time71); } //下列輸出的各行依次是下列各個算法的函數 cout << "版本一（左側樞紐） " << "版本一（非遞歸法） " << "版本一（右側樞紐） " << endl; cout << "版本二（直接交換） " << "版本三（單向劃分） " << "版本四（隨機樞紐） " << "版本五（三數取中）" << endl; for (int j = 0; j < 7; ++j) { int sum = 0; vector<int>::iterator iter = vec_time[j].begin(); while (iter != vec_time[j].end()) { cout << *iter << " "; sum += *iter; ++iter; } cout << (double)sum / 10; cout << endl; } ~~~  分析： 從上圖可以得出如下結論： （1）版本一以左側元素或右側元素作為樞紐時，兩種方式的遞歸算法性能相當； ??????? 但是使用STL的棧適配器的非遞歸算法性能很差，幾乎是遞歸算法時間的二倍。這是所有算法中性能最差的算法；這原因可能是STL實現的棧比較耗時。一百萬隨機數排序平均時間為6.8秒。 （2）版本二：Hore算法（每次直接交換）性能略微優于版本一（產生空穴）。 （3）版本三：單向劃分（兩個指針都從待排序數組一側開始移動）性能較差，僅次于上述的非遞歸算法。 （4）版本四：隨機樞紐算法性能和版本一的非遞歸算法性能類似。 （5）版本五：三數取中算法是所有算法中性能最好的。一百萬隨機數平均時間只有2.5秒。 ### （3）隨機產生一千萬個數，連續測試10次 采用和上一節同樣的方式測試，只是測試數據量提高了一個數量級：由一百萬個數提升到一千萬個。  分析： （1）對比一百萬數據測試和一千萬數據測試可以看出，同樣是快速排序，其性能差距也會很大： 一百萬隨機數時最慢算法（非遞歸算法）時間幾乎是最快的算法（三數取中）的時間的2.7倍； 一千萬隨機數測試時，最慢算法（單向劃分算法）的時間是最快的算法（三數取中）時間的11倍還多。 （2）一百萬個數據時，Hore算法（每次直接交換）性能略微優于版本一（產生空穴）；在一千萬個數據時，Hore算法（每次直接交換）性能遠優于版本一（產生空穴），后者時間是前者的3倍還多。 （2）一百萬數據測試的最差算法是非遞歸，一千萬算法測試最差算法是單向劃分。其實一百萬數據測試時，單向劃分的表現就不佳。 ### 三、已經有序數組排序測試 使用有序的數組測試排序性能，已經知道，在數組有序的情況下，快速排序的性能退化為O(n ^? 2)。因此不能如隨機數據測試那樣，測試百萬、千萬級別的數據。 事實上，當已排序數組元素超過5000個（大概數值）時，我的程序就崩潰了（在初始數組有序（或逆序）情況下，棧深度為O(n)，棧溢出，所以程序崩潰。參考[基礎排序算法總結](http://blog.csdn.net/u013074465/article/details/44346135)）。 測試程序和隨機數的類似，只是初始化是將數組元素初始化為有序的，而不是隨機的： ~~~ //有序數據測試的代碼片段 //將數組初始化為4000個元素的有序數組 for (int a = 0; a < 10; ++a) { int max = 100; //每次測試的都是隨機的一百萬個數 int i = 0; vector<int> ivec1, ivec1_none, ivec12, ivec2, ivec3, ivec4, ivec5; for (i = 0; i < 4000; i++) { int value = i; ivec1.push_back(value); ivec1_none.push_back(value); ivec12.push_back(value); ivec2.push_back(value); ivec3.push_back(value); ivec4.push_back(value); ivec5.push_back(value); } ~~~ ### （1） 2000個數  ### （2）3000個數  ### （3） 4000個數  分析： 雖然測試數據比較少，但是仍可以看出：單向劃分算法性能較差。三數取中算法性能占絕對優勢。 ### 結論： （1）采用待排序序列第一個或最后一個元素作為樞紐的算法性能：在平均情況下不錯，可以從隨機數的測試中看出來，但是當待排序的數組序列基本有序或逆序時，請算法性能退化為O(n ^ 2)。其中非遞歸版本算法性能沒有遞歸版本好，可能是STL棧實現性能不夠好。 （2）三數取中樞紐法的性能是最優解法的，它不僅可以避免初始序列基本有序或逆序的最壞情況，相反，在初始序列基本有序或逆序時，該算法達到的是最好的性能：每次樞紐將待排序序列劃分為等長的兩個子序列，此時棧空間最小，僅為longn，所需時間也最少。 （3）單向劃分的性能不佳，采用待排序序列第一個或最后一個元素作為樞紐的非遞歸版本性能也不佳。