[實驗]遞歸與分治政策之合并排序和快速排序比較

一、實驗内容：

随機産生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;
}