第2章 算法基础

2.1、插入排序

排序问题：
输入：n个数的序列<a1，a2，···， an>。
输出：输入序列的一个排列<a'1，a'2，···， a'n>，满足a'1<=a'2<=···<=a'n。（依次从小到大排列）
插入排序实现的伪代码：

    for j = 1 to A.length-1
        key = A[j];
        i = j - 1;
        while(i > 0 and A[i] > key)
            A[i+1] = A[j];
            i = i - 1;
        A[i+1] = key;

2.2、分析算法

分析算法，也就是预测算法需要的资源。
分析算法是，假定都是在RAM（随机访问机）中实现的，指令一条接一条的执行，没有并发操作。

c为大于等于1的常量
n为输入。
算法的程序运行时间，与其输入规模相关。
输入规模的概念，根据不同的研究问题而有不同的描述。
插入排序最快的运行时间为：an+b
最坏的运行时间为：an^2+bn+c
本书后面，往往只集中于求最坏情况的运行时间。
因为对于插入排序来说，平均情况的结果也是an^2+b*n+c，和最坏情况一样。

最终关心的是，运行时间的增长量级，所以只考虑公式中的最重要的项，a*n^2。
如果一个算法的最坏情况运行时间比另一个算法具有更低的增加量级，那么通常认为，前者比后者更有效。（输入规模n越大，低量级的算法越快）

2.3、设计算法

插入排序使用了增量法。。下来介绍“分治法”的设计方法。

2.3.1、分治法

分治法的思想：
将原问题分解为几个规模较小但类似原问题的子问题，递归地求解这些子问题，再合并这些子问题的解来建立原问题的解。
归并排序算法
完全遵循分治模式，其操作如下：

1. 分解：分解待排序的n个子元素的序列，成各有n/2个元素的子序列；
2. 解决：使用归并排序递归的排序这两个子序列；
3. 合并：合并两个已排序的子序列以产生已排序的答案。

当待排序的子序列长度为1时，递归开始回升。
归并排序的关键操作，在于“合并”步骤中两个已排序的子序列。
归并排序运行时间为0(n* lg n)
足够大输入时，归并排序要比插入排序快。