#include "stdafx.h"#include <iostream>#include <ctime>using namespace std;int a[1000000];int tempA[1000000];#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+1;    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;        //递归分解的过程，细分区域直到每个区域元素个数小于等于2        mergeSort(a, l, m-1);        mergeSort(a, m+1, r);        //归并过程        merge(a, l, m, r);    }}void printArray(int a[], int length){    cout << "数组内容：";    for(int i = 0; i < length; i++)    {        if(i == 0)            cout << a[i];        else            cout << "," << a[i];    }    cout << endl;}int _tmain(int argc, _TCHAR* argv[]){    float tim;    for (int i = 0; i < 1000000; i++)    {        a[i] = int(rand() % 100000);    }    BEGIN_RECORD    //printArray(a, sizeof(a)/sizeof(int));    mergeSort(a, 0, sizeof(a)/sizeof(int)-1);    //printArray(a, sizeof(a)/sizeof(int));    END_RECORD(tim)        cout << "运行时间：" << tim << "s" <<  endl;    system("pause");    return 0;}