处理海量数据的三大排序之——归并排序（C++）

#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;
}