第1章 算法在计算机中的作用

　　本章是本书的开篇，介绍了什么是算法，为什么要学习算法，算法在计算机中的地位及作用。

　　算法（algorithm）简单来说就是定义良好的计算机过程，它取一个或一组值作为输入，并产生出一个或一组值作为输出。即算法就是一系列的计算步骤，用来将输入数据转换成输出数据。

　　书中有一句话非常好：

　　Having a solid base of algorithm knowledge and technique is one characteristic that separates the truly skilled programmers from the novices.

　　是否具有扎实的算法知识和技术基础，是区分真正熟练的程序员与新手的一项重要特征。
以这句话激励自己要努力学习算法，夯实基础，成为真正熟练的程序员。

第二章 算法基础

　本章通过介绍插入排序和归并排序两种常见的排序算法来说明算法的过程及算法分析，在介绍归并排序算法过程中引入了分治（divide-and-conquer）算法策略。

1、插入排序

　　输入：n个数（a1,a2,a3,...,an）

　　输出：输入序列的一个排列（a1',a2',a3',...an'）使得（a1'≤a2'≤a3'≤...≤an'）。

　　插入排序的基本思想是：将第i个元素插入到前面i-1个已经有序的元素中。具体实现是从第2个元素开始（因为1个元素是有序的），将第2个元素插入到前面的1个元素中，构成两个有序的序列，然后从第3个元素开始，循环操作，直到把第n元素插入到前面n-1个元素中，最终使得n个元素是有序的。该算法设计的方法是增量方法。书中给出了插入排序的为代码，并采用循环不变式证明算法的正确性。
插入排序算法的分析

　　算法分析是对一个算法所需的资源进行预测，资源是指希望测度的计算时间。插入排序过程的时间与输入相关的。插入排序的最好情况是输入数组开始时候就是满足要求的排好序的，时间代价为θ(n)，最坏情况下，输入数组是按逆序排序的，时间代价为θ(n^2)。
2、归并排序

　　归并排序采用了算法设计中的分治法，分治法的思想是将原问题分解成n个规模较小而结构与原问题相似的小问题，递归的解决这些子问题，然后再去合并其结果，得到原问题的解。分治模式在每一层递归上有三个步骤：

分解（divide）：将原问题分解成一系列子问题。
解决（conquer）：递归地解答各子问题，若子问题足够小，则直接求解。
合并（combine）：将子问题的结果合并成原问题的解。

归并排序（merge sort）算法按照分治模式，操作如下：
分解：将n个元素分解成各含n/2个元素的子序列
解决：用合并排序法对两个序列递归地排序
合并：合并两个已排序的子序列以得到排序结果

　　在对子序列排序时，长度为1时递归结束，单个元素被视为已排序好的。归并排序的关键步骤在于合并步骤中的合并两个已经有序的子序列，引入了一个辅助过程，merge(A,p,q,r)，将已经有序的子数组A[p...q]和A[q+1...r]合并成为有序的A[p...r]。书中给出了采用哨兵实现merge的伪代码，课后习题要求不使用哨兵实现merge过程。在这个两种方法中都需要引入额外的辅助空间，用来存放即将合并的有序子数组，总的空间大小为n。