C语言算法基础之

假设给定我们两个都是升序的数组，要求我们要把这两个数组以升序的方式合并到一个数组中，则我们就可以在这两个数组中分别各拿取一个元素进行比较，将二者之间较小值先放在这个新数组中，以此类推。举个例子，有两个数组{4，5}和{3，6}，首先我们将第一个数组中的元素{4}和第二个数组中的元素{3}进行比较，{3}为较小者，所以将其放在要合并到的数组的第一个位置上，然后在比较第一个数组中的{4}和第二个数组中的第二个元素{6}，二者{4}为较小者，所以将其放在要合并到的新数组的第二个位置上，以此类推，最终合并的数组为{3，4，5，6}。

但是这种情况只适用于两个数组都是有序的情况下，如果给的是无序的数组那么应该怎么做呢？之前我们在快速排序中讲到过，当一个数组没有或者只有一个元素的时候，那么他就是一个有序数组。根据这种思想，我们是不是可以先将这个无序的数组进行分割，当分割成的部分都是只具有一个或者没有元素构成的时候，这种情况是不是就都是有序的数组了呢？然后我们在实行刚刚说到的将两个有序数组合并到一个数组中，以此类推，分割之后在进行合并，最终就会得到一个有序的数组了。

归并排序的思想就是将两个有序的数组合并成一个有序的数组。

第一步：将数组进行分解，当分解成单个元素为一组的时候才是组内有序的。

第二步：将每两个有序数组视作一对，将每一对都合并成一个有序的数组，重复第二步，直至排序完成。合并的步骤：先申请两数组合并后所需要的空间，然后用“合并两个有序数组”的方法将每一对都合并到一个空间内。

 代码如下：