#include "stdafx.h"

#include <iostream>

#include <ctime>

using namespace std;

int a[];

int tempA[];

#define BEGIN_RECORD            \

{                                \

clock_t ____temp_begin_time___;    \

____temp_begin_time___=clock();

#define END_RECORD(dtime)        \

dtime=float(clock()-____temp_begin_time___)/CLOCKS_PER_SEC;\

}

/*

    归并排序的合并过程

    a - 待排序数组

    l - 排序区域左边界

    m - 排序区域中点

    r - 排序区域右边界

*/

void merge(int a[], int l, int m, int r)

{

    int i = l;

    int j = m+;

    int k;

    //int tempA[100000];    //空间复杂度O(n),在最后一次合并需要用到n个临时存储空间

    //将两个有序排序区域合并成一个有序区域

    //part1：两排序区域都从索引N（0,1...n）开始比较大小，取较小的值push进临时数组，同时该排序区域比较索引+1；当任一排序区域的值取完后，结束part1

    for (k = l; i <= m && j <= r; k++)

    {

        if(a[i] <= a[j])

        {

            tempA[k] = a[i++];

        }

        else

        {

            tempA[k] = a[j++];

        }

    }

    //part2：将另一排序区域剩余的值按有序push进临时数组。此时临时数组为合并的有序区域。结束part2

    if(i <= m)

        for (; k <= r; k++)

            tempA[k] = a[i++];

    if(j <= r)

        for (; k <= r; k++)

            tempA[k] = a[j++];

    //part3：将临时数组数据拷贝到原数组。排序结束

    for (int k = l; k <= r; k++)

    {

        a[k] = tempA[k];

    }

}

/**

    归并排序

    时间复杂度O(n*logn)，

    空间复杂度O(n)

    在需要稳定排序的情况下，归并排序是最

    在不考虑稳定性的情况下，归并排序由于需要O(n)的临时存储空间，比较耗费内存，效果不如快速排序

*/

void mergeSort(int a[], int l, int r)

{

    int m;

    if(l < r)

    {

        m = (l + r)/;

        //递归分解的过程，细分区域直到每个区域元素个数小于等于2

        mergeSort(a, l, m-);

        mergeSort(a, m+, r);

        //归并过程

        merge(a, l, m, r);

    }

}

void printArray(int a[], int length)

{

    cout << "数组内容：";

    for(int i = ; i < length; i++)

    {

        if(i == )

            cout << a[i];

        else

            cout << "," << a[i];

    }

    cout << endl;

}

int _tmain(int argc, _TCHAR* argv[])

{

    float tim;

    for (int i = ; i < ; i++)

    {

        a[i] = int(rand() % );

    }

    BEGIN_RECORD

    //printArray(a, sizeof(a)/sizeof(int));

    mergeSort(a, , sizeof(a)/sizeof(int)-);

    //printArray(a, sizeof(a)/sizeof(int));

    END_RECORD(tim)

    cout << "运行时间：" << tim << "s" <<  endl;

    system("pause");

    return ;

}