一般我们说快速排序的数组是有序的时候，排序的时间复杂度回退滑道O(n^2)，这是因为如果每次都去边上的数字作为pivot值，就会导致排序之后的不平衡，也可以说是一颗不平衡树，这里我们采取的优化策略就是需要将pivot随机生成，这样才能保证分开的数组不会那么不平衡，从而继续递归。
但是还有一种情况，就是要排序的数组中重复的元素很多，这个时候当随机选取pivot的时候，发现时间复杂度又退化成了O(n^2)了，这种情况如下： 面对元素e看是大于v，还是小于v，进而放到相应的part当中继续递归，但是我们没有考虑到当e=v的时候是什么情况。如果e=v的话，那么橙色的部分可以是<=v的部分元素。
我们可以发现，不管把e放到<=v还是>=v的部分，都很有可能把数组分成极度不平衡的两部分，一旦重复元素过多，选择的pivot也不太好，此时就会造成这种不平衡的情况。就退化了。 如何解决？使用两路快排！
我们将i指向的元素向右找，如果是小于v的那就继续向右，当找到e>=v的时候停止，同理，j从右向左扫描，当e<=v的时候就停止。之后们交换一下这两个e元素如下： 紧接着i朝右查看下一个，j朝左查看下一个元素，直到i和j元素重合，实际上，当i，j遍历到的数是相等的情况，我们交换一下顺序，这样就能使得数分散在不同的part，进而就不会有那么不平衡。
#include <iostream> #include <algorithm> #include <ctime> #include "SortTestHelper.h" #include "MergeSort.h" #include "InsertionSort.h" using namespace std; // 对arr[l...r]部分进行partition操作 // 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p] template <typename T> int _partition(T arr[], int l, int r){ // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot swap( arr[l] , arr[rand()%(r-l+1)+l] ); T v = arr[l]; int j = l; for( int i = l + 1 ; i <= r ; i ++ ) if( arr[i] < v ){ j ++; swap( arr[j] , arr[i] ); } swap( arr[l] , arr[j]); return j; } // 双路快速排序的partition // 返回p, 使得arr[l...p-1] <= arr[p] ; arr[p+1...r] >= arr[p] // 双路快排处理的元素正好等于arr[p]的时候要注意，详见下面的注释：） template <typename T> int _partition2(T arr[], int l, int r){ // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot swap( arr[l] , arr[rand()%(r-l+1)+l] ); T v = arr[l]; // arr[l+1...i) <= v; arr(j...r] >= v int i = l+1, j = r; while( true ){ // 注意这里的边界, arr[i] < v, 不能是arr[i] <= v // 思考一下为什么? while( i <= r && arr[i] < v ) i ++; // 注意这里的边界, arr[j] > v, 不能是arr[j] >= v // 思考一下为什么? while( j >= l+1 && arr[j] > v ) j --; // 对于上面的两个边界的设定, 有的同学在课程的问答区有很好的回答:) // 大家可以参考: http://coding.imooc.com/learn/questiondetail/4920.html if( i > j ) break; swap( arr[i] , arr[j] ); i ++; j --; } swap( arr[l] , arr[j]); return j; } // 对arr[l...r]部分进行快速排序 template <typename T> void _quickSort(T arr[], int l, int r){ // 对于小规模数组, 使用插入排序进行优化 if( r - l <= 15 ){ insertionSort(arr,l,r); return; } // 调用双路快速排序的partition int p = _partition2(arr, l, r); _quickSort(arr, l, p-1 ); _quickSort(arr, p+1, r); } template <typename T> void quickSort(T arr[], int n){ srand(time(NULL)); _quickSort(arr, 0, n-1); } // 比较Merge Sort和双路快速排序两种排序算法的性能效率 int main() { int n = 1000000; // 测试1 一般性测试 cout<<"Test for random array, size = "<<n<<", random range [0, "<<n<<"]"<<endl; int* arr1 = SortTestHelper::generateRandomArray(n,0,n); int* arr2 = SortTestHelper::copyIntArray(arr1,n); SortTestHelper::testSort("Merge Sort", mergeSort, arr1, n); SortTestHelper::testSort("Quick Sort", quickSort, arr2, n); delete[] arr1; delete[] arr2; cout<<endl; // 测试2 测试近乎有序的数组 // 双路快速排序算法也可以轻松处理近乎有序的数组 int swapTimes = 100; cout<<"Test for nearly ordered array, size = "<<n<<", swap time = "<<swapTimes<<endl; arr1 = SortTestHelper::generateNearlyOrderedArray(n,swapTimes); arr2 = SortTestHelper::copyIntArray(arr1, n); SortTestHelper::testSort("Merge Sort", mergeSort, arr1, n); SortTestHelper::testSort("Quick Sort", quickSort, arr2, n); delete[] arr1; delete[] arr2; cout<<endl; // 测试3 测试存在包含大量相同元素的数组 // 使用双快速排序后, 我们的快速排序算法可以轻松的处理包含大量元素的数组 cout<<"Test for random array, size = "<<n<<", random range [0,10]"<<endl; arr1 = SortTestHelper::generateRandomArray(n,0,10); arr2 = SortTestHelper::copyIntArray(arr1, n); SortTestHelper::testSort("Merge Sort", mergeSort, arr1, n); SortTestHelper::testSort("Quick Sort", quickSort, arr2, n); delete[] arr1; delete[] arr2; return 0; }对于循环条件当中的arr[i]<v以及arr[i]<=v的选择如下：
