using namespace std;
#include
#include
#include “SortTestHelper.h”
#include “InsertionSort.h”
#include "mergeSort.h"
using namespace std;
////方法

// 对arr[l…r]部分进行partition操作
// 返回p, 使得arr[l…p-1] < arr[p] ; arr[p+1…r] > arr[p]

template
int _partition(T arr[],int l,int r)
{
//定义当前数组的初始中间值。当作是l.(暂时)
T v = arr[l];

int j =l;
for(int i = l+1;i<=r;i++)

    if(arr[i] < v)
    {
        swap(arr[j+1],arr[i]);
        j++;
    }

swap(arr[l],arr[j]);
return j;

}

template
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)
{
//针对数组，从0 到n-1 的数据排序
_quickSort(arr,0,n-1);
}

int main()
{

int n =  500000;

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;


return 0;

}