前一节论述了快速排序算法基本有序排列时的两种优化方法。 本节对新的测试用例进行测试。 测试的使用示例如下所示。
int main ()//测试-要排序的列具有大量重复值的int n=400000； int * arr=sorttesthelper :3360 generaterandomarray (n，0，10 )； int * arr2=sorttesthelper :3360 copy intarray (arr，n )； sorttesthelper : testsort (' mergesort '，merge sort，arr，n )； sorttesthelper : testsort (' quciksort2'，quickSort，arr2，n )； 删除[ ] arr； delete[] arr2； 返回0； }测试结果如下。
这样，在数据量多、重复数据多的情况下，即使是前一节优化的高速排序算法也不能允许时间性能，但是这里针对这样的重复数据量多的情况进一步优化高速排序算法。
首先，让我们看一下__patition ()函数的操作。
在templatetypenametint _ patition (tarr [ ]，int l，int r ) ) arr[l.r]中随机选择一个元素作为标定点，然后与序列中的第一个元素进行swap ) arr [ int j=l； for(intI=L1； i=r； I () if ) arr[i] ) swap ) arr[i]，arr[i]； j； }swap(arr[L]，arr[j]； 返回j； }在if语句中，将v的要素放置在橙色部分，=v的要素全部放置在紫色部分。
在排列中大量存在重复元素情况下，即大量存在与v相等的元素的情况下，最终如下述：所示变得极端不均衡
这样得到的快速递归树也是不均衡的，树的深度超过logn，总时间复杂度比O(nlogn )大很多，退化为O(n^2)的时间复杂度。
因此，关于快速排序的算法，采取了如下所示的另一种思想，即不是将v和v的部分都配置在数组的1头，而是分别配置在数组的左右2头。
其次，I，j分别指橙色部分的下一个要素和紫色部分的前一个要素，在arr[i]v的情况下，继续I直到I所指的要素e=v，然后看右边的j所指的要素，在arr[j]v的情况下，j所指的要素e=v为止如图所示：
然后交换arr[i]和arr[j]的值。 此时，左边的部分成为=v的部分，右边的部分成为=v的部分，可以将=v的要素均匀地分散在v和v的部分。 以下表示。
该patition过程持续到在i=j时停止为止。 具体的c实现代码如下所示。
SortTestHelper.h文件(包括辅助函数)
# include iostream # includecstdlib # include ctime/clock (，clocks _ per _ sec # includecassert///包含函数assert ) ) using ng generaterandomarray(intn，int RangeL，int RangeR ) /返回数组的起始地址(//rangel=rangel )//参数是表达式，如果表达式为真，则返回true Srand(Time(0)； for(intI=0； i n； I ) {arr[I]=rand(% ) ranger-range L1 } Rangel； //使出现的随机数介于RangeL和RangeR之间()； (//辅助函数-生成几乎规则的随机排列int * generatenearlyorderedarray (intn，int swapTime )
int *arr = new int[n]; for(int i = 0; i < n; i++) { arr[i] = i; //先生成一个完全有序的数组 } //然后交换几组元素，使之变成无序但近乎有序的数组 srand(time(0)); for(int j = 0; j < swapTime; j++) { //随机生成一个x位置和y位置 int posx = rand() % n; int posy = rand() % n; //交换x和y处的元素 swap(arr[posx], arr[posy]); } return arr; } //辅助数组 - 产生一个完全有序数组 int* generateTotallyOrderedArray(int n) { int *arr = new int[n]; for(int i = 0; i < n; i++) { arr[i] = i; } return arr; } //辅助函数 - 打印数组 template<typename T> void printArray(T arr[], int n) { for(int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << endl; } //辅助函数 - 判断数组是否有序（升序） template<typename T> bool isSorted(T arr[], int n) { for(int i = 0; i < n - 1; i++) { if(arr[i] > arr[i + 1]) { return false; } } return true; } //辅助函数 - 测试算法的时间 template<typename T> void testSort(string sortname, void(*sort)(T[], int), T arr[], int n) //arr[]和n是函数指针需要的参数 { clock_t starttime = clock(); sort(arr, n); //调用函数sort() clock_t endtime = clock(); //判断排序是否成功 assert(isSorted(arr, n)); //若是数组无序，则assert会自动调用abort()退出程序，不会执行下面的语句 cout << sortname << " needs " << double(endtime - starttime) / CLOCKS_PER_SEC << "s." << endl; } //辅助函数 - 拷贝数组 int* copyIntArray(int a[], int n) { int *arr = new int[n]; //使用C++函数copy() copy(a, a + n, arr); return arr; }}main.cpp文件#include <iostream>#include <ctime>#include <cstdlib>#include "SortTestHelper.h"using namespace std;template<typename T>int __patition(T arr[], int l, int r){ swap(arr[l], arr[rand() % (r - l + 1) + l]); T v = arr[l]; int i = l + 1, j = r; while(true) { while(i <= r && arr[i] < v) { i++; } while(j >= l + 1 && arr[j] > v) { j--; } if(i > j) { break; } swap(arr[i++],arr[j--]); } swap(arr[j], arr[l]); return j;}template<typename T>void __quickSort(T arr[], int l, int r){ if(l >= r) { return; } else { int p = __patition(arr, l, r); __quickSort(arr, l, p - 1); __quickSort(arr, p + 1, r); }}template<typename T>void quickSort(T arr[], int n){ srand(time(0)); __quickSort(arr, 0, n - 1);}int main(){ int a[10] = {10, 3, 6, 2, 4, 8, 5, 1, 7, 0}; quickSort(a, 10); SortTestHelper::printArray(a, 10); return 0;} 测试结果如下：
在main函数中测试该快排算法和归并排序算法针对有大量重复数据的序列的排序时间性能：
main.cpp文件
#include <iostream>#include <ctime>#include <cstdlib>#include "SortTestHelper.h"using namespace std;template<typename T>int __patition(T arr[], int l, int r){ swap(arr[l], arr[rand() % (r - l + 1) + l]); T v = arr[l]; int i = l + 1, j = r; while(true) { while(i <= r && arr[i] < v) { i++; } while(j >= l + 1 && arr[j] > v) { j--; } if(i > j) { break; } swap(arr[i++],arr[j--]); } swap(arr[j], arr[l]); return j;}template<typename T>void __quickSort(T arr[], int l, int r){ if(l >= r) { return; } else { int p = __patition(arr, l, r); __quickSort(arr, l, p - 1); __quickSort(arr, p + 1, r); }}template<typename T>void quickSort(T arr[], int n){ srand(time(0)); __quickSort(arr, 0, n - 1);}//归并排序template<typename T>void __merge(T arr[], int l, int mid, int r) //[l...r]（前闭后闭）{ T aux[r - l + 1]; for(int i = l; i <= r; i++) //i是aux的下标 { aux[i - l] = arr[i]; } //i、j是arr中的下标,k是arr中的下标 //i-l、j-l是aux中的下标 int i = l, j = mid + 1, k = l; while(i <= mid && j <= r) { if(aux[i - l] < aux[j - l]) { arr[k++] = aux[i - l]; i++; } else { arr[k++] = aux[j - l]; j++; } } //出界条件 while(i <= mid) { arr[k++] = aux[i - l]; i++; } while(j <= r) { arr[k++] = aux[j - l]; j++; }}template<typename T>void __mergeSort(T arr[], int l, int r){ if(l >= r) { return; } else { int mid = (l + r) / 2; //对左半部分arr[l...mid]进行归并排序 __mergeSort(arr, l, mid); //再对右半部分arr[mid + 1...r]进行归并排序 __mergeSort(arr, mid + 1, r); //然后将排好序的左右两部分归并到一起 __merge(arr, l, mid, r); }}template<typename T>void mergeSort(T arr[], int n){ //传递一个数组，调用归并排序算法归并arr[0...n-1] __mergeSort(arr, 0, n - 1);}int main(){ int n = 400000; int *arr = SortTestHelper::generateRandomArray(n, 0, 10); int *arr2 = SortTestHelper::copyIntArray(arr, n); SortTestHelper::testSort("mergeSort", mergeSort, arr, n); SortTestHelper::testSort("quickSort", quickSort, arr2, n); delete[] arr; delete[] arr2; return 0;} 测试结果如下：
可以看出，此时的快排算法针对待排序列存在大量重复数据的情况下的时间性能已经和归并排序差不多甚至要好。实际上该快速排序算法不仅在这种情况，并且在待排序列无序、待排序列基本有序的情况下，时间性能都很好。
下一小节将继续改进我们的快排算法，使其在待排序列拥有大量重复键值的情况下，效率更高。