归并排序解释

归并排序 Merge Sort 是典型的分治法的应用，其算法步骤完全遵循分治模式。

分治法思想

分治法 思想: 将原问题分解为几个规模较小但又保持原问题性质的子问题，递归求解这些子问题，然后再合并这些子问题的解，最终得到原问题的解。

分治模式每层递归步骤

1、分解原问题为若干个子问题；
2、解决子问题。递归求解子问题，当子问题规模足够小时，可以直接求解；
3、合并这些子问题的解构成原问题的解。

归并排序的分治模式

1、分解未排序 n 个元素的序列成 各有 n/2 个元素的连续子序列；
2、递归排序两个连续子序列；
3、合并两个已排序的连续子序列构成整个完成排序的序列。

归并排序递归树

我们以序列 [7, 4, 8, 1, 3, 5, 6, 2] 为例构建一个归并排序的递归树

上半部分递归树为将当前长度为 n 的序列拆分成长度为 n/2 的子序列，下半部分递归树为合并已经排序的子序列。

时间复杂度

假设时间复杂度为 T(n)，在递归解决当前两个规模为 n/2 的子问题时，我们需要消耗 2T(n/2)* 的时间。
在合并过程中，对于一个具有 n 个元素的序列，我们需要消耗O(n)的时间。

故时间复杂度如下

归并排序核心代码

void Merge(int a[], int left, int mid, int right){
    int temp[right - left + 1];                   //临时数组用于存储排序时的数
    int i = left;                                 //分成两块 i指向左边的数字 j指向右边的数字 
    int j = mid + 1;
    int k = 0;                                    //k用于存储数字到临时数组

    while( i <= mid && j <= right ){
    	if(a[i] < a[j])    	                  //永远都是 i 和 j 指向的数进行比较
    	    temp[k++] = a[i++];                   //谁小，谁就先放到临时数组中
    	else
    	    temp[k++] = a[j++];
    }

    while( i <= mid )                             //如果左边还有数没放上去，就依次放上去
    	temp[k++] = a[i++];
    while( j <= right )                           //如果是右边还有同上
    	temp[k++] = a[j++];
    
    for(int m = left, n = 0; m <= right; m++, n++)//读取临时数组中的数
    	a[m] = temp[n];
}


void Merge_Sort(int a[], int left, int right){
    if( left == right )
    	return;

    int mid = (left + right)/2;
    //递归拆分成较小规模子序列排序 
    Merge_Sort(a, left, mid);            
    Merge_Sort(a, mid + 1, right);
    Merge(a, left, mid, right);      //合并较小规模问题解
}

完整程序源代码

#include<iostream>
#include<ctime>
using namespace std;

void Merge(int a[], int left, int mid, int right){
    int temp[right - left + 1];                   //临时数组用于存储排序时的数
    int i = left;                                 //分成两块 i指向左边的数字 j指向右边的数字 
    int j = mid + 1;
    int k = 0;                                    //k用于存储数字到临时数组

    while( i <= mid && j <= right ){
    	if(a[i] < a[j])    	                  //永远都是 i 和 j 指向的数进行比较
    	    temp[k++] = a[i++];                   //谁小，谁就先放到临时数组中
    	else
    	    temp[k++] = a[j++];
    }

    while( i <= mid )                             //如果左边还有数没放上去，就依次放上去
    	temp[k++] = a[i++];
    while( j <= right )                           //如果是右边还有同上
    	temp[k++] = a[j++];
    
    for(int m = left, n = 0; m <= right; m++, n++)//读取临时数组中的数
    	a[m] = temp[n];
}


void Merge_Sort(int a[], int left, int right){
    if( left == right )
        return;

    int mid = (left + right)/2;
    //递归拆分成较小规模子序列排序 
    Merge_Sort(a, left, mid);            
    Merge_Sort(a, mid + 1, right);
    Merge(a, left, mid, right);      //合并较小规模问题解
}


void Show(int a[], int n){
    for(int i = 0; i < n; i++)
        cout<<a[i]<<" ";
    cout<<endl;
}


main(){
    int a[50];
    srand((int)time(0));
    for(int i = 0; i < 50; i++)
        a[i] = rand() % 100 + 1;
    Show(a, 50);

    Merge_Sort(a, 0, 50);
    
    cout<<endl<<endl;
    Show(a, 50);
}

程序运行结果图