算法导论(1)——写好伪代码

　　在学习各种编程语言的时候，数据结构与算法一般都会作为重点课程来指出。而谈到算法，算法导论一书又常常被大家提起。然而作为一个编程界的老鸟，技术层面的菜鸟，最近才开始啃算法导论，实属令自己汗颜。不过拾起总比放下的要好，所以这里根据自己的理解做一些记录。并在阅读初期就设定了一些目标，包括理解并学习各种常用算法及其设计思路，学习并写好伪代码等。

什么是算法

　　书中讲到，算法就是任何良定义的计算过程。算法的目的是解决问题。问题陈述说明了期望的输入和输出，而算法则描述一个特定的计算过程来实现输入输出的关系。

算法的描述（伪代码）

　　算法可以使用英语说明，也可以用中文说明，当然也可以说明成计算机程序。它的唯一要求是这个说明必须精确的描述所需要遵循的计算过程。
　　我个人更欣赏将算法描述为用一种伪代码书写的程序。它的优势在于，能够使用最清晰最简洁的方法来说明给定的算法。并且根据伪代码可以将算法转化成各种所需的编程语言。

如何写好伪代码

　　在我们常用的编程语言中，通常按照所需的命名规范和运算逻辑的使用，讲所想的用该语言展示出来。伪代码同样也可以按照相似的方法展示。其实伪代码并没有明确的规范要求，但是在算法导论一书中，他列出了一些所谓的约定。当然，这些约定我们可以不去遵守。但是如果按着约定去书写伪代码的话，会使我们的伪代码变得清晰易懂，何乐不为。

缩进表示块结构。参考python的语言结构。　
while,for,if-else等结构具有和c语言等相同的解释。但是方便理解，我们去除额外的细节，表示重点。比如当一个for循环时，当循环上升时使用to，下降时使用downto，步数使用by。
//表示注释
变量直接使用无需声明。一般变量默认为局部变量。
数据访问通过数组名和下标的方式访问。
使用error表示过程中出现错误。

　　伪代码的使用方法和约定都比较宽松，目的都是能够写出清晰易懂的伪代码。

伪代码实践

这里列举一个插入排序的算法的伪代码实现，大家一起来感受一下气场。

INSERT-SORT(A)
    for j=2 to A.length
        key=A[j]
        // Insert A[j] into the sorted sequence A[1..j-1].
        i = j-1;
      while i>0 and A[i]>key
          A[i+1]=A[j]
          i = i-1
      A[i+1]=key

归并排序(merge sort)

MERGE(A,p,q,r)
        n1=q-p+1
        n2=r-q
        let L[0..n1] and R[0..n2] be a new array
        for i = 0 to n1-1
                L[i]=A[p+i]
        for j = 0 to n2-1
                R[j]=A[q+1+j]
        L[n1]=∞
        L[n2]=∞
        i=0
        j=0
        for k = p to r
                if L[i] < R[j]
                        A[k]=L[i]
                        i = i + 1
                else
                        A[k]=R[j]
                        j = j +1
MERGE-SORT(A,p,r)
        if(p<r)
                q=[(p+r)/2]
                MERGE-SORT(A,p,q)
                MERGE-SORT(A,q+1,r)
                MERGE(A,p,q,r)