[实验]递归与分治策略之合并排序和快速排序比较

一、实验内容：

随机产生20组数据，第一组500000个，第二组1000000个，以此类推，到第20组10000000个，数据范围为（0,100000），对同一组数据进行合并排序和快速排序，记录运行时间，结果如下：

二、实验结果

接连结果均相差无几。可以做一个数据可视化分析（此处就不放图了 作业刚刚提交 避免误会）

三、实验分析与结论

从以上分析得出排序同一组数据，当数据量较少时，QuickSort的运行时间比MergeSort的运行时间少，随着数据增加，MergeSort的运行时间比QuickSort的运行时间少。

四、源代码：

#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <string>

using namespace std;

int A[10000001];//数据数组
int C[10000001];//复制数组
int B[10000001];//辅助数组

//初始化，随机产生n个数据保存在C数组中
void Initialize(int n)
{
    srand((unsigned)time(0));
    for(int i = 1 ; i <= n ; i++)
        C[i] = rand()%100000;
}

//复制C数组元素到A数组
void CopyCtoA(int n)
{
    for(int i = 1 ; i <= n ; i++)
        A[i] = C[i];
}


//Merge
void Merge(int A[], int low, int mid, int high)
{
    int s = low , t = mid + 1 , k = low;

    //将小元素添加到辅助数组
    while( s<=mid && t<=high )
    {
        if(A[s]<=A[t])
        {
            B[k] = A[s];
            s = s + 1;
        }
        else
        {
            B[k] = A[t];
            t = t + 1;
        }
        k = k + 1;
    }

    if(s == mid + 1)
    {
        //把A[t...high]中剩余的元素复制到B数组
        for(int i = k ; i <= high ; i++)
            B[i] = A[t++];
    }
    else
    {
        //把A[s...mid]中剩余的元素复制到B数组
        for(int i = k ; i <= high ; i++)
            B[i] = A[s++];
    }

    //把B数组复制到A数组
    for(int j = low ; j <= high ; j++)
        A[j] = B[j];
}

//MergeSort
void MergeSort(int A[], int low, int high)
{
    if(low < high)
    {
        //把数组分成两部分分别排序在合并
        int mid = (low+high)/2;
        MergeSort(A , low , mid);
        MergeSort(A , mid+1 , high);
        Merge(A , low , mid , high);
    }
}


//Split
int Split(int A[],int low,int high)
{
     A[0]=A[low];
     int key=A[low];
     while(low<high)
     {
         while((low<high)&&(A[high]>=key))
            high--;
         if(low<high) 
             A[low++]=A[high]; 
         while((low<high)&&(A[low]<=key)) 
            low++;
         if(low<high)
            A[high--]=A[low]; 
     }
     A[low]=A[0];
     return low;
}

//QuickSort
void QuickSort(int A[], int low, int high)
{
    int mid;
    if(low < high)
{
		//把数组划分成两部分
        mid = Split(A, low, high); 
        QuickSort(A, low, mid-1); 
        QuickSort(A, mid+1, high); 
    }
}


//对n个数执行合并排序或快速排序，计算输出执行时间
void Sort_ExcutionTime(int n , string sort_type)
{
    CopyCtoA(n);
    clock_t start, end;
    double totaltime;

    if(sort_type == "MergeSort")
    {
        start = clock();
        MergeSort(A, 1, n);
        end = clock();
    }
    else if(sort_type == "QuickSort")
    {
        start = clock();
        QuickSort(A, 1, n);
        end = clock();
    }

    totaltime = (double)(end-start)/CLOCKS_PER_SEC*1000;
    cout<<sort_type<<" running time is: "<<totaltime<<" ms"<<'\n';
}

//执行程序
void Excute()
{
    for(int i = 1 ; i <= 20 ; i++)
    {
        Initialize(500000*i);
        cout<<"n="<<500000*i<<'\n';
        Sort_ExcutionTime(500000*i, "MergeSort");
        Sort_ExcutionTime(500000*i, "QuickSort");
        cout<<'\n';
    }
}

int main()
{
    Excute();
    return 0;
}