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

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

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

  调用每个层有三个步骤:

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

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

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

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

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

  排序算法主要集中在合并操作上,抛开递归,我们单独分析合并操作。首先我们把哨兵牌放在两堆的底部,可以理解为扑克牌之王。它是一个特殊值,所以为了简化,我们在这里放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;//表示数组中不能出现的无限数字

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