从排序开始（三）归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并操作的过程如下：

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2.设定两个指针，最初位置分别为两个已经排序序列的起始位置

3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

4.重复步骤3直到某一指针达到序列尾

5.将另一序列剩下的所有元素直接复制到合并序列尾

简单地说，归并排序就是将序列不断地划分，直到每个序列只有一个元素（一个元素的序列肯定是有序的），然后这些有序序列不断归并，合成新的有序序列，最后，归并成全部有序的序列。

这幅 Wiki 的图很直观地解释了归并排序：

最差时间复杂度 O(n logn)

最优时间复杂度 O(n)

平均时间复杂度 O(n logn)

稳定性：稳定

实现：

#include <iostream>  
  
using namespace std;  
  
//归并操作，将有两个个有序数列 num[start...mid] 和 num[mid...end] 归并并。  
//归并至 sorted 序列，然后复制回原数组  
void merge(int num[], int start, int mid, int end, int sorted[])  
{  
    int i = start, j = mid + 1;  
    int m = mid,   n = end;  
    int k = 0;  
      
    //每次比较两个元素，直到某个序列到达末尾  
    while (i <= m && j <= n)  
    {  
        if (num[i] <= num[j])  
            sorted[k++] = num[i++];  
        else  
            sorted[k++] = num[j++];  
    }  
      
    //将序列中剩余元素直接复制到 sorted 序列尾  
    while (i <= m)  
        sorted[k++] = num[i++];  
      
    while (j <= n)  
        sorted[k++] = num[j++];  
      
    //将排序好的序列写回原数组  
    for (i = 0; i < k; i++)  
        num[start + i] = sorted[i];  
}  
  
void mergesort(int a[], int start, int end, int sorted[])  
{  
    if (start < end)  
    {  
        //进行分治  
        int mid = (start + end) / 2;  
        mergesort(a, start, mid, sorted);      
        mergesort(a, mid + 1, end, sorted);   
        merge(a, start, mid, end, sorted);   
    }  
}  
  
bool MergeSort(int num[], int n)  
{  
    int *p = new int[n];  
    if (p == NULL)  
        return false;  
    mergesort(num, 0, n - 1, p);  
    delete[] p;  
    return true;  
}  
  
//简单测试,建议数据不要太大，那是在刷屏啊 o(╯□╰)o  
int main()  
{  
    int n;  
    //测试 n 个随机数的排序  
    while(cin>>n)  
    {  
        int *p = new int[n];  
        if (!p)  
        {  
            cout<<"Failed..."<<endl;  
            continue;  
        }  
        for(int i=0;i<n;++i)  
            p[i] = rand();  
        bool flag = MergeSort(p,n);  
        if(!flag)  
        {  
            cout<<"Failed..."<<endl;  
            continue;  
        }  
        for(int i=0;i<n;++i)  
            cout<<p[i]<<' ';  
        cout<<endl;  
        delete []p;  
    }  
    return 0;  
}

补充：软件开发 , C++ ,