排序 | 归并排序 Merge Sort

【算法】归并排序

归并排序(Merge Sort)就是将两个或两个以上的有序表合并成一个有序表的过程。

归并排序的思想：

假设初始序列有n个数据，则可以看成n个有序的子序列，每个子序列的长度都为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并......如此重复，直到得到一个长度为n的有序序列为止。

其中，将两个有序表合并成一个有序表的过程称为2-路归并，2-路归并最为简单和常用，故以2-路归并为例（平常的归并排序也多以2-路归并）。

分治思想

相邻两个有序子序列的归并(合并)：【治的过程】

基本思想：
假设两个有序子序列存储在同一数组的相邻位置上，分别为arr[begin...mid]和arr[mid+1...end]，每次分别从这两个有序子序列中各取出一个值进行比较，将较小者放入数组temp中。重复此过程，直至其中一个子序列为空，最后将另一个子序列中剩余部分直接复制到数组temp中。

下面以有序子序列[4,5,7,8]和[1,2,3,6]为例，进行归并(合并)。

归并排序
代码：

//将两个子序列arr[begin...mid]和arr[mid+1...end]归并(合并) 
void merge_core(int arr[], int begin, int mid, int end)
{
    int i=begin, j=mid+1, k=1; // i:第一个子序列的下标起点
                               // j:第二个子序列的下标起点 
                              // k:数组temp的下标起点(从1开始) 
    int *temp = new int[end-begin+2];// end-begin+1:两个子序列的总长度(数组长度) 
                                     // 那为什么要end-begin+2?这是因为数组temp下标从1开始，而不是从0开始 
                                     // 动态申请内存空间 
    while(i<=mid && j<=end) // 将两个子序列的值由小到大地并入数组temp 
    {
        if(arr[i]<=arr[j])// 比较两子序列的值 
        {
            temp[k++]=arr[i++];
        }
        else 
        {
            temp[k++]=arr[j++];
        }
    }
    while(i<=mid)// 将剩余的arr[begin...mid]复制到temp中 
    {
        temp[k++]=arr[i++];
    }
    while(j<=end)// 将剩余的arr[mid+1...mid]复制到temp中 
    {
        temp[k++]=arr[j++];
    }
    // 将临时的数组temp中的数据copy到待排序的数组arr 
    int count=1;// 数组temp的下标起点(从1开始) 
    for(int t=begin;t<=end;t++)
    {
        arr[t]=temp[count++];
    }
    delete[]temp;// 释放temp数组空间 
}   // Time：O(n), Space：O(n)

归并排序：【分和治】

步骤：
当序列长度等于1时(即begin==end)，递归结束。否则：
① 将当前序列一分为二，求出分裂点mid=(begin+high)/2。
② 对子序列arr[begin...mid]递归，进行递归排序。
③ 对子序列arr[mid+1...end]递归，进行递归排序。
④ 调用merge_core算法，将有序的两个子序列arr[begin...mid]和arr[mid+1...end]归并为一个有序的序列arr[begin...end]。
代码：

// Split arr[] into two parts [begin,mid), [mid,end)
// and using merge_core to merge this two parts
// Total Time：O(nlogn)
void merge_sort(int arr[], int begin, int end)
{
    if (end==begin) return; // 如果当前序列只有一个元素，则结束递归 
    int mid = (begin+end)>>1; //【另一种写法：mid = (begin+end)/2;】 
                              // 将当前序列一分为二，求出分裂点mid 
    merge_sort(arr,begin,mid);// 对子序列arr[begin...mid]递归归并排序 
    merge_sort(arr,mid+1,end);// 对子序列arr[mid+1...end]递归归并排序 
                              // Time：O(logn)   
    merge_core(arr,begin,mid,end);// 将子序列arr[begin...mid]和arr[mid+1...end]归并(合并) 
} 

完整代码：【C++版】

// 实现方式多种多样，这里的代码仅供参考
#include<iostream>
#include<cstdio>
using namespace std;

//将两个子序列arr[begin...mid]和arr[mid+1...end]归并(合并) 
void merge_core(int arr[], int begin, int mid, int end)
{
    int i=begin, j=mid+1, k=1; // i:第一个子序列的下标起点
                               // j:第二个子序列的下标起点 
                              // k:数组temp的下标起点(从1开始) 
    int *temp = new int[end-begin+2];// end-begin+1:两个子序列的总长度(数组长度) 
                                     // 那为什么要end-begin+2?这是因为数组temp下标从1开始，而不是从0开始 
                                     // 动态申请内存空间 
    while(i<=mid && j<=end) // 将两个子序列的值由小到大地并入数组temp 
    {
        // 比较两子序列的值
        if(arr[i]<=arr[j]) temp[k++]=arr[i++];
        else temp[k++]=arr[j++];
    }
    // 将剩余的arr[begin...mid]复制到temp中 
    while(i<=mid) temp[k++]=arr[i++];
    // 将剩余的arr[mid+1...mid]复制到temp中 
    while(j<=end) temp[k++]=arr[j++];

    // 将临时的数组temp中的数据copy到待排序的数组arr 
    int count=1;// 数组temp的下标起点(从1开始) 
    for(int t=begin;t<=end;t++) arr[t]=temp[count++];

    delete[]temp;// 释放temp数组空间 
}   // Time：O(n), Space：O(n)

// Split arr[] into two parts [begin,mid), [mid,end)
// and using merge_core to merge this two parts
// Total Time：O(nlogn)
void merge_sort(int arr[], int begin, int end)
{
    if (end==begin) return; // 如果当前序列只有一个元素，则结束递归 
    int mid = (begin+end)>>1; //【另一种写法：mid = (begin+end)/2;】 
                              // 将当前序列一分为二，求出分裂点mid 
    merge_sort(arr,begin,mid);// 对子序列arr[begin...mid]递归归并排序 
    merge_sort(arr,mid+1,end);// 对子序列arr[mid+1...end]递归归并排序 
                              // Time：O(logn)   
    merge_core(arr,begin,mid,end);// 将子序列arr[begin...mid]和arr[mid+1...end]归并(合并) 
} 

int n; //待排序序列的长度 
int arr[200010]; //存放待排序序列的数组 

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)// 下标从1开始 
    {
        scanf("%d",&arr[i]);
    }
    merge_sort(arr,1,n);// 归并排序 O(nlogn)
    for(int i=1;i<=n;i++) // 下标从1开始 
    {
        printf("%d ",arr[i]);
    }
    printf("\n");
    return 0;
} 

运行结果

STL中的Merge：

STL中merge函数的作用：将两个有序的序列合并为一个有序的序列。

函数原型：merge(first1,last1,first2,last2,result,compare);

• firs1t：第一个容器的首迭代器
• last1：第一个容器的末迭代器
• first2：第二个容器的首迭代器
• last2：容器的末迭代器
• result：存放结果的容器
• compare：比较函数（可缺省，默认值 → 合并为一个升序序列）。

PS：注意是要两个子序列是有序的，才能合并成一个有序的序列。

算法分析：

• 时间复杂度：
  归并排序在形式上类似一棵二叉树，它需要遍历的次数就是二叉树的深度。根据完全二叉树，可以得出它的时间复杂度是O(n*log2n)。
  即，当有n个值时，需要进行log2n趟归并排序。在每一趟归并中，其值的比较次数不超过n，元素移动次数都是n。因此归并排序的时间复杂度为O(n*log2n)。
• 空间复杂度：
  用顺序表(线性结构)实现归并排序时，需要一个大小为n的临时存储空间，来保存合并序列。故空间复杂度为O(n)。

算法特点：

• 是稳定排序。
• 可用于链式结构，且不需要附加存储空间，但递归实现时仍需要开辟相应的递归工作栈。

写在最后

参考资料：

• 《数据结构(C语言版) (第2版)》严蔚敏
• CSDN博客：http://www.cnblogs.com/jingmoxukong/p/4308823.html
• 算法图片来源：https://www.cnblogs.com/chengxiao/p/6194356.html
• 博客：www.cnblogs.com/jingmoxukong/p/4308823.html