归并排序的算法思想,归并排序算法分析

　　算法回顾介绍中解释的第一个算法是归并排序。我们将合并排序分为两步。第一步是考虑如何归并，第二步是把问题分成多个归并排序和归并。这是典型的分而治之的想法。

　　调用每个层有三个步骤：

　　分解：将原问题分解成若干个子问题。

　　求解：求解这些子问题，递归求解每个子问题。如果子问题规模足够小，直接求解。

　　合并：将这些子问题的解合并到原问题的解中。

　　用分而治之的前提是问题是线性的，可以合并。如果是非线性的，使用分而治之的时候问题会变得非常复杂。

　　我们把合并后的数组理解为扑克牌，先分成两堆牌，然后合并。当然，价值不会是扑克牌的价值。你可以想象一下，你手里有和他要排序的值一样的扑克牌。

　　排序算法主要集中在合并操作上，抛开递归，我们单独分析合并操作。首先我们把哨兵牌放在两堆的底部，可以理解为扑克牌之王。它是一个特殊值，所以为了简化，我们在这里放100；结果就是，每当哨兵牌露出来的时候，他不可能是更小的牌，除非两堆都已经露出了哨兵牌。但一旦这样，我们的合并行动就结束了。因为我们事先知道，刚刚执行r-p 1的卡会被放在输出堆里。

　　代码如下：

　　#包含stdio.h

　　#包括iostream

　　使用命名空间std

　　void Merge(int* A，int p，int q，int r)

　　int n1=q-p 1；

　　int N2=r-q；

　　int * L=new int[n1 1]；

　　int * R=new int[N2 1]；

　　l[n1]=100；//表示数组中不能出现的无限数字

　　r[N2]=100；//表示数组中不能出现的无限数字