归并排序算法C++实现（超详细解析！！！！）

目录

一、前言

（1）分治算法

（2）分治算法解题方法

    1.分解：

    2.治理：

    3.合并

二、归并排序

1.问题分析

2.算法设计

    （1）分解：

    （2）治理：

    （3）合并：

3.算法分析

三、AC代码

 四、共勉

一、前言

（1）分治算法

    归并排序，其实就是一种分治算法 ，那么在了解归并排序之前，我们先来看看什么是分治算法。在算法设计中，我们引入分而治之的策略，称为分治算法，其本质就是将一个大规模的问题分解为若干个规模较小的相同子问题，分而治之。

（2）分治算法解题方法

    1.分解：

    将要解决的问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。

    2.治理：

    求解各个子问题。由于各个子问题与原问题形式相同，只是规模较小而已，而当子问题划分得足够小时，就可以用简单的方法解决。

    3.合并

    按原问题的要求，将子问题的解逐层合并构成原问题的解。

二、归并排序

1.问题分析

    归并排序是比较稳定的排序方法。它的基本思想是把待排序的元素分解成两个规模大致相等的子序列。如果不易分解，将得到的子序列继续分解，直到子序列中包含的元素个数为1。因为单个元素的序列本身就是有序的，此时便可以进行合并，从而得到一个完整的有序序列。

2.算法设计

    （1）分解：

    将待排序的元素分成大小大致一样的两个子序列。

    （2）治理：

    对两个子序列进行个并排序。

    （3）合并：

    将排好序的有序子序列进行合并，得到最终的有序序列。

3.算法分析

    首先我们先给定一个无序的数列（42，15，20，6，8，38，50，12），我们进行合并排序数列，如下图流程图所示：

 步骤一：首先将待排序的元素分成大小大致相同的两个序列。

步骤二：再把子序列分成大小大致相同的两个子序列。

步骤三：如此下去，直到分解成一个元素停止，这时含有一个元素的子序列都是有序的。

步骤四：进行合并操作，将两个有序的子序列合并为一个有序序列，如此下去，直到所有的元素都合并为一个有序序列。

 举例，下面我将以序列（4，9，15，24，30，2，6，18，20）进行图解。

（1）初始化：i = low，j = mid+1，mid = (low+hight)/2 ，申请一个辅助数组 b

int* b = new int[hight - low + 1];  //用 new 申请一个辅助函数
	int i = low, j = mid + 1, k = 0;    // k为 b 数组的小标

 （2）现在比较 a [i]  和 b[j]  ，将较小的元素放在 b 数组中，相应的指针向后移动，直到 i > mid 或者 j>hight 时结束。

while (i