C/C++实现双路快速排序算法原理

// QuickSort2.cpp : 双路快速排序，适用于解决有很多重复数据的数组。
//

#include "stdafx.h"
#include "E:/学习/C++/数据结构和算法/code/算法/排序算法/common/sortTestHelper.h"
#include "QuickSort.h"
#include "RadomQuickSort.h"
#include "QuickSort2.h"

using namespace std;

int main()
{
 int n = 100000;
 int *arr1 = SortTestHelper::generateRadomArray(n, 0, 50);
 int *arr2 = SortTestHelper::generateRadomArray(n, 0, 50);
 int *arr3 = SortTestHelper::generateRadomArray(n, 0,50);
 SortTestHelper::sortTime("随机快速排序", RadomQuickSort, arr1, n);
 SortTestHelper::sortTime("快速排序", QuickSort, arr2, n);
 SortTestHelper::sortTime("双路快速排序", QuickSort2, arr3, n);
 delete[] arr1;
 delete[] arr2;
 delete[] arr3;
 return 0;
}

#ifndef QUICKSORT2_H
#define QUICKSORT2_H

#include 
#include 
using namespace std;

template 
int __partition3(T *arr, int l, int r)
{
//此处结合随机快速排序的算法进行了优化，标记点在数组里随机选择
 int RAND = (rand() % (r - l + 1) + l);
 swap(arr[RAND], arr[l]);

 int v = arr[l];
 int i = l + 1;
 int j = r;
 while (true)
 {
 while (i <= r&&arr[i] = l + 1 && arr[j] > v) j--;
 if (i > j)
 {
 break;
 }
 swap(arr[i], arr[j]);
 i++;
 j--;
 }
 swap(arr[l], arr[j]);
 return j;
}

template 
void __QuickSort2(T *arr,int l,int r)
{
 if (l>=r)
 {
 return;
 }
 int p = __partition3(arr, l, r);
 __QuickSort2(arr, l, p - 1);
 __QuickSort2(arr, p + 1, r);
}

template 
void QuickSort2(T *arr, int n)
{
 __QuickSort2(arr, 0,n-1);
}


#endif

#ifndef RADOMQUICKSORT_H
#define RADOMQUICKSORT_H

#include 
#include 

using namespace std;

template 
int __Randpartition(T *arr, int l, int r)
{
 //选择开头的数作为分割的数
 int RAND = arr[rand() % (r - l + 1) + l];
 swap(arr[l], RAND);
 int i = arr[l];
 //遍历数组，使得arr[l,l+1,...j]arr[l]
 int j = l;
 //如果当前数据大于arr[l]，就无需改变位置，如果小于arr[l]，就将当前数据与分割点的数据后一个数据交换
 for (size_t k = j + 1; k <= r; k++)
 {
 if (arr[k]
void __RadomQuickSort(T *arr, int l, int r)
{
 if (l >= r)
 {
 return;
 }
 int p = __Randpartition(arr, l, r);
 __RadomQuickSort(arr, l, p - 1);
 __RadomQuickSort(arr, p + 1, r);
}

template 
void RadomQuickSort(T *arr, int n)
{
 __RadomQuickSort(arr, 0, n - 1);
}

#endif

#ifndef QUICKSORT_H
#define QUICKSORT_H

using namespace std;

template 
int __partition(T *arr, int l, int r)
{
 //选择开头的数作为分割的数
 int i = arr[l];
 //遍历数组，使得arr[l,l+1,...j]arr[l]
 int j = l;
 //如果当前数据大于arr[l]，就无需改变位置，如果小于arr[l]，就将当前数据与分割点的数据后一个数据交换
 for (size_t k = j + 1; k <= r; k++)
 {
 if (arr[k]
void __QuickSort(T *arr, int l, int r)
{
 if (l >= r)
 {
 return;
 }
 int p = __partition(arr, l, r);
 __QuickSort(arr, l, p - 1);
 __QuickSort(arr, p + 1, r);
}

template 
void QuickSort(T *arr, int n)
{
 __QuickSort(arr, 0, n - 1);
}

#endif

#ifndef SORTTESTHELPER_H
#define SORTTESTHELPER_H

#include 
#include 
#include 
#include 

using namespace std;

namespace SortTestHelper 
{
//产生一个从[rangeL,rangeH]的随机数组，数组个数是n
 int* generateRadomArray(int n,int rangeL,int rangeH)
 {
 //为了算法的健壮性，需要判断错误输入
 assert(rangeL 
 void printArr(T *arr,int n)
 {
 for (size_t i = 0; i 
 bool ifSort(T *arr,int n)
 {
 for (size_t i = 0; i arr[i+1])
 {
 return false;
 }
 }
 return true;
 }

//计算程序运行时间
 template
 //函数输入参数是：所需要计算的运行的函数的名称，函数的指针，函数的输入数组，输入数组的个数
 void sortTime(string funName,void(*sort)(T*arr, int), T* arr,int n)
 {
 clock_t startime = clock();
 sort(arr,n);
 clock_t endtime = clock();

 assert(ifSort(arr, n));
 std::cout <