我们都知道

#include<iostream>
#include<ctime>
using namespace std;
 
//MergeSort
void Merge(int a[ ], int p, int q, int r)
{
//对两个有序的数列进行归并
    int i,k;
    int begin1,end1,begin2,end2;
    int *temp= new int[r-p+1];
    begin1= p;
    end1 = q;
    begin2 = q+1;
    end2 = r;
    k = 0;
    //数列a从begin1到end1，及从begin2到end2都是有序的，接下来把这两部分合成一个
    //新的有序的数列
    while((begin1 <= end1)&&( begin2 <= end2)){
        if(a[begin1] <=a[begin2]){
            temp[k] = a[begin1];
            begin1++;
        } else {
            temp[k] = a[begin2];
            begin2++;
        }
        k++;
    }
    while(begin1<=end1){
        temp[k++] = a[begin1++];
    }
    while(begin2<=end2){
        temp[k++] = a[begin2++];
    }
    for (i = 0; i < (r - p+1); i++){
        a[p+i] = temp[i];
    }
    delete temp;
}
 
void MergeSort(int a[], int first, int last)
{
    int mid = 0;
    if(first<last){
        mid = (first+last)/2;
        MergeSort(a, first, mid);
        MergeSort(a, mid+1,last);
        Merge(a,first,mid,last);
    }
}
 
//QuickSort
void QuickSort(int a[],int first,int last)
{
    int pivot,last_small;
    pivot=a[first];
    last_small=first;
    //从pivot之后的第一个元素开始扫描，一旦发现比pivot小的元素就挪到前边
    //循环结束后，从a[1]到a[last_small]都是比pivot小的元素
    //从a[last_small+1]到a[last]都是不比pivot小的元素
    for(int i=first+1;i<=last;i++){
        if(a[i]
<pivot){
            last_small++;
            swap(a[last_small],a[i]);
        }
    }
    //这个swap的作用是使得从a[0]到a[last_small-1]都是比pivot小的元素
    //从a[last_small+1]到a[last]都是不比pivot小的元素
    swap(a[first],a[last_small]);
    if(first<last){
        QuickSort(a,first,last_small-1);
        QuickSort(a,last_small+1,last);
    }
}
 
int main()
{
    int *p,*q,t=2;;
    int choice;
    clock_t start,end;
    const int num=1000;
    p=new int[num];
 
    srand(int(time(NULL)));
    for(int i=0;i<num;i++){
        p[i]=rand()%num;
        cout<<p[i]<<"\t";
    }
 
    q=new int[num];
    for(int i=0;i<num;i++){
        q[i]=p[i];
    }
 
    cout<<endl;
    cout<<"Input 1 to use mergesort,input 2 to use quicksort:"<<endl;
    while(t--){
        cin>>choice;
        switch(choice){
        case 1:
              start=clock();
              MergeSort(p,0,num-1);
              end=clock();
              for(int i=0;i<num;i++){
                  cout<
<p[i]<<"\t";
              }
              cout<<"Time of sort is "<<double(end-start)/CLOCKS_PER_SEC<<endl;
              break;
         case 2:
            start=clock();
            QuickSort(q,0,num-1);
            end=clock();
            for(int i=0;i<num;i++){
                 cout<<q[i]<<"\t";
            }
            cout<<"Time of sort is "<<double(end-start)/CLOCKS_PER_SEC<<endl;
            break;
          }
     cout<<endl;
    }
    return 0;
}