一个小白的算法学习之路。读《算法导论》第一天。本文仅作为学习的心得记录。
算法（Algorithm）
对于一个程序员来说，无论资历深浅，对算法一词的含义一定会或多或少有自己的体会，在《算法导论》中，作者在第一章就将算法定义为一种计算过程。
我们第一次遇到算法，首先关心的必定是算法的正确性，有些人可能不耐烦了，这正确性有什么好说的，三岁小孩都能分辨一条简单算法对不对。的确，正确的算法就是以正确结果结束的算法。（废话！！！）但是错误的算法就不那么简单了，错误的算法有时以错误的结果结束，有时甚至不会结束（依旧废话。。。。。。）但是！！如果你认为错误的算法一无用处，那就大错特错了。不正确的算法其实只要错误率可控，有时可能是有用的。
为什么要学习算法
事实上，许多人或许都认为学习算法是没有必要的，毕竟如果我要写一个排序程序，只要去算法手册上找一下，就会找到无数种算法。这让学习算法看上去就似乎可有可无了。但算法真正的魅力，在于它永远处于科技发展的最前端。只使用已有的算法并不是学习《算法导论》这本书的真正目的，因为市面上的任何一本算法教程都可以满足你的需求（虽然很多内容也都来源于《算法导论》），处在科技前沿，学会把不可能变为可能才是学习这本书的真正含义。这本书在教授你从如何分析算法到如何设计算法这一个过程，这才是我看这本书的目的，而不仅仅是为了学习其中的算法。
插入排序（Insertion Sort）
既然有算法，就必定有其对应的问题，首先我们先引入一个问题
排序问题：
输入：n个数的一个序列<a1,a2,...,an>
输出：输入序列的一个排序<b1,b2,...,bn>,其b1≤b2≤...≤bn
如果你不想下次看到插入排序这个词语，却只有一种似曾相识的感觉，然后急忙去google上copy代码的话，那首先很重要的一点就是建立直观印象。当然，这个算法的直观印象其实早就在我们脑海里根深蒂固了，我们都玩过斗地主，牌发到自己手里，第一个反映就是整理自己的牌，右手从牌堆里拿出一张，插在左手已经排好顺序的牌的正确位置，并且不断重复。我们很容易建立起了对插入排序的第一印象。不过计算机代码毕竟有别于现实生活，如何将这个直观的过程通过代码实现呢？
让我们首先从我们脑海里仅有的直观印象开始分析，从牌堆里拿出一张牌，这就是数组中的取值操作，而排到正确位置这就似乎不再那么直观，一般我们习惯从小到大开始比较牌的大小然后把牌插进去，但是数组就不那么容易随随便便插入一个值，要想插入一个值，必须把插入地方之后的元素都向后移动一位。可见这个方法有些麻烦，那我们便换一种方法，从大到小的比较，如果要插入的值比与之比较的值小便把与之比较的值在数组中的位置向后移动一位。这样算法的实现便开始清晰明了起来。
伪代码：
INSERTION-SORT（A）for j=2 to A.lengthkey=A[j] //从牌堆里拿出一张牌i=j-1 //与插入值比较的元素下标//进行比较while i>0 and A[i]>keyA[i+1]=A[i] //把比插入值大的元素在数组中向后移动一位i=i-1 //再比较数组中前一个值A[i]=key //将牌插入正确的位置当然这是一个极其简单的算法，这样注释或许有一些小题大作，但是这是理解算法的一个很好的例子。我们可以仔细观察整个算法过程（我相信通过上面的解释很容易在脑海中运行整个算法的运算过程），我们会发现，在整个算法运行的过程当中A[1...j-1]是始终是有序的，毕竟直观印象上左手的牌肯定是一直有序的。这些性质被表示为循环不变式，事实上它的主要作用就是帮助我们理解算法的正确性。我们应该也已经清晰的感觉到了。
插入算法分析
分析算法，是我们学习整本书最基础的技能，毕竟只有学会分析算法，在我们自己设计算法时才能分析自己算法的性能和所需的资源
Analysis of Algorithm is theoretical study of computer program's performance and resource usage ——Charles E.Leiserson
这里我们更多的关注算法的性能，也就是计算时间。
如果必须非常严谨的分析，我们需要考虑实现算法的模型，‘运行时间’和‘输入规模’的定义之类复杂的问题，但就我目前看完第二章看来除了增加分析的严谨并没有带来其他显而易见的好处，所以在此我准备忽略这些繁琐的先决条件，让我们先假设一行简单的伪代码需要的运行时间为常数c。
这样让我们开始分析上面的伪代码，首先我们需要表示出每一行伪代码运行的时间及运行的次数
INSERTION-SORT（A）            代价（时间）                        次数
for j=2 to A.length c1 nkey=A[j] c2 n-1i=j-1 c3 n-1while i>0 and A[i]>key c4 T1 A[i+1]=A[i] c5 T2i=i-1 c6 T3A[i]=key c7 n-1
其中T1=$$\sum_{j=2}^nt_j$$
T2=T3=$$\sum_{j=2}^n(t_j-1)$$
而$$t_j$$表示的就是在第j次（事实上是第j-1次）For循环中while循环的循环次数。
列出了代价和次数，接下来很容易能求得：
$$T（n）=c_1n+c_2(n-1)+c_3(n-1)+c_4\sum_{j=2}^nt_j+c_5\sum_{j=2}^n(t_j-1)+c_6\sum_{j=2}^n(t_j-1)+c_7(n-1)$$
接下来一个小小的问题就是如何化简这个看似很长的公式，如果我们仔细观察，便会发现，化简这道公式并不是很难，只有一个问题，就是我们并不知道$$t_j$$等于什么，因为每次输入的序列不同，tj便会不一样，这也可见其实输入的数据对算法的性能同样有影响。如果我们需要继续分析下去（其实也必须要分析下去，不然上面那个公式啥也看不出来），便需要开始分情况讨论（初中，高中最讨厌老师说这道题要分情况讨论。。。结果大了还是逃不了这命运。）
最佳情况：
首先是最佳情况，很容易看出，最佳情况就是压根不移动数组，插入的值已经在合适的位置，那么$$t_j=1$$
T(n)很容易就可以化简出来（我就不再算了）
我们可以简单表示为$$T(n)=an+b$$
这是一个线性函数
最坏情况
然后是最坏情况，就是插入值必须和之前的每一个数比较过去，那么while循环就一共就比较了j次（算上最后一次退出循环比较的那次），那么$$t_j=j$$
然后又经过了一系列简单的化简T（n）可以表示为$$an^2+bn+c$$
因此他是n的二次函数
总结
在一般情况下我们更加关心算法的最坏情况，主要有一下三点原因
1、我们可以保证这个算法一定能在某个时间内完成。
2、有些算法，最坏情况经常出现。
3、平均情况常常和最坏情况一样坏（你可以试一下tj=j/2的情况）
归并排序（Merge Sort）
说到归并排序不得不提到分治法这个概念。要记住的 是分治法每层递归都有三个步骤：分解、解决、合并。
那先让我们看一下归并排序是如何实现这三个步骤的
分解：分解待排序的n个元素的序列成为各具有n/2个元素的子序列（让我们暂且假定其为偶数，我们会发现奇偶数对程序的影响并不大）
解决：递归的解决两个子序列
合并：合并两个已排序的子序列产生答案
这个算法和上一个算法相比依旧不算很难，但是递归或许对我这样的小白来说有些抽象，但是用通俗的话概括这整个过程，其实就是把一个序列先一半一半切切成小块再重新装起来的过程。当序列分解到长度为1时，便开始重新组装这个序列。由此不难看出，整个归并算法重点就是如何组装这个序列，或者说重点就在于合并。
所以如果我们解决了如何合并两个已排序的子序列，整个归并排序基本上就完成了。那如何解决合并这个问题呢？我们希望最后得到的序列按从小到大的顺序排列，第一步自然而然想到的便是找到最小的一个元素，由于我们现在有的是两个已经排序的序列，所以最小的元素必定是这两个序列的最小元素中的一个（或两个，如果这两个序列最小元素相等的话）这样来看伪代码便清晰了许多。还需要提的一点是，如果一个序列中元素用完，另一个序列中剩下的元素便是已排好序的可以直接添加到合并的序列当中，为了实现这个判断，我们设定一个哨兵值，放在两个序列末尾。
伪代码：
MERGE（A，p,q,r）n1=q-p+1 //两个序列的长度n2=r-q //两个序列的长度let L[1...n1+1] and R[1...n2+1] be new arraysfor i= 1 to n1L[i]=A[p+i-1]for j=1 to n2R[j]=A[q+j]L[n1+1]= ∞ R[n2+1]= ∞ //以上代码是创建两个新数组，并赋值i=1j=1 for k=p to r //接下来便是寻找两个数组中最小的元素if L[i]≤R[j]A[k]=L[i]i=i+1elseA[k]=R[j]j=j+1我们可以用之前说的循环不变量来证明此过程的正确性，在此不再赘述。
解决了最关键的合并部分，接下来实现归并算法便非常容易了，只是之前归并算法描述的翻译，以下是伪代码：
MERGE-SORT（A,p,r）if p<rq=(p+r)/2 //分解MERGE-SORT(A,p,q) //解决MERGE-SORT(A,q+1,r) //解决MERGE(A,p,q,r) //合并需要注意的是，if语句其实就是对最小规模问题的直接求解，最小规模情况就是只有一个元素的时候，即我们什么都不需要做，只需要停止递归就行。
