归并排序

归并排序和快速排序有类似之处，同样采用分治法，不同的是，归并排序不选取基准值，采用递归方式直接将数据分为两个区间，再进行排序合并。需要注意的是，排序实际是从最小单位，即分区大小为1时开始的。

时间复杂度

因为都是从中间划分区间，且无基准值。归并排序时间复杂度较稳定

O(nlogn)

步骤

1. 对半划分区间
2. 递归，直到分区大小为1
3. 依次合并区间

以本次代码的数据为例，原始数据为：

第一次划分区间后为：

左分区第二次划分：

左分区第三次划分：

左分区第四次划分：

随后合并分区得到：

再次合并：

直到完成合并

代码实现

/*归并排序*/

#include <iostream>
using namespace std;


int *Merge( int *arr1, int len1, int *arr2, int len2 ) //从小到大合并值
{
    int *arr3 = new int[len1 + len2];
    int p1 = 0, p2 = 0, p3 = 0;

    while ( p1 < len1 && p2 < len2 )
    {
        if ( p1 < len1 && arr1[p1] <= arr2[p2] )
        {
            arr3[p3++] = arr1[p1++];
        }
        else
        {
            arr3[p3++] = arr2[p2++];
        }
    }

    //收尾处理
    while ( p1 < len1 )
    {
        arr3[p3++] = arr1[p1++];
    }

    while ( p2 < len2 )
    { 
        arr3[p3++] = arr2[p2++]; 
    } 
    return arr3; 
} 
void MergeSort( int *arr, int len )
{ 
    int *arr1 = new int[len / 2]; 
    int *arr2 = new int[len - len / 2]; 
    if ( len > 1 )
    {
        for ( int i = 0; i < len / 2; i++ )
        {
            arr1[i] = arr[i];
        }

        MergeSort( arr1, len / 2 );//分治递归

        for ( int i = 0; i < len - len / 2; i++ )
        {
            arr2[i] = arr[len / 2 + i];
        }

        MergeSort( arr2, len - len / 2 );//分治递归
        int *date = Merge( arr1, len / 2, arr2, len - len / 2 );

        for ( int i = 0; i < len; i++ )
        {
            arr[i] = date[i];
        }

        delete date;
    }
}

int main()
{
    int arr[] = {10, 15, 14, 85, 45, 62, 312, 47, 51, 84, 99, 78, 41};
    int len = sizeof( arr ) / sizeof( arr[0] );
    MergeSort( arr, len );
    int i = 0;

    while ( i < len )
    {
        cout << arr[i++] << endl;
    }

    return 0;
}

执行结果