归并排序解释

归并排序 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);

}

巴特西

[排序算法] 归并排序 (C++)