第一章：算法在计算中的作用
算法的定义：简单的说就是定义良好的计算过程，由输入得到输出！
算法的作用：应用非常广泛，许多问题都涉及到算法！
算法的重要性：是否拥有扎实的算法知识和技术基础，是区分真正熟练的程序员与新手的一项重要特征。
第二章 算法入门
学习算法的目的，不仅仅是很快理解算法然后编出相应的程序，很重要的一点是算法的设计上面，因为设计算法要考虑到比如时间复杂度，空间复杂度等因素，而会不会正确分析，事先估计算法的这些因此，也是非常重要的，这也是算法导论这本书重点介绍的一个内容！
插入排序是对少量元素进行排序的有效算法！插入排序的关键在于，还是利用原来的数组，进行增量排序，首先通过比较后面的元素与已经排好顺序的数组的元素，将当前比较的元素插入到适当的位置，插入的过程其实就是移动数组元素的过程！
其实现程序如下：
/*------------------------------------------------- * Copyright: 2011-2013 * FileName : InsertSort.cpp * Des: C++实现插入排序算法 * * Author: 马小波 * Date: 2011-4-1 * History: 1.0 * Other : ---------------------------------------------------*/ #include <iostream> #include <assert.h> using std::cout; using std::endl; const int SORTNUM = 10;//the sort number template<class T> T* InsertSort (T* SortArray); int main (int argv, char ** argc) { int i; int SortArray[SORTNUM] = {5,2,1,6,4,3,12,11,7,9};//简单int数组，没有实现模板数组 InsertSort(SortArray); cout<<"the sorted Array :"; for (i = 0; i < SORTNUM; i++) { cout.width(3); cout<<SortArray[i]; } cout<<endl; return 0; } /*---------------------------------------------------------- * Function: InsertSort * Des: 插入排序实现函数 * Call: * Called By: main * Input: T* SortArray 待排序数组 * OutPut: * Return: T* 排好序的数组 * Author: 马小波 2011-4-1 * Other : -----------------------------------------------------------*/ template<class T> T* InsertSort (T* SortArray) { assert(SortArray != NULL); int i, j; T * temp; temp = SortArray;//copy point T key = 0;//the key volue for (j = 1; j < SORTNUM; j++) { key = temp[j];//当前要插入的键值 //已经排好序的序列 for (i = j - 1; i >= 0; i--) { if (temp[i] > key)//将当前temp[i]移向后一位 { temp[i+1] = temp[i]; } else { break;//找到要插入键值的位置 } } temp[i+1] = key;//将键值插入到当前位置 } return temp; }
循环不变式和插入排序的正确性分析：
循环不变式的性质：
（1）初始化：在第一轮循环之前，应该正确。在第一次循环之前，已经排列好的子数组A[1]，当然正确。
（2）保持：如果循环的某一次迭代开始前正确，那么下一次迭代开始前也应该是正确的。下标j代表要插入的元素，在每一次循环结束后，内循环代表的子数组的元素按照顺序排列好，外循环剩余的元素则是剩余没有排好顺序的，整个数组的元素也是不变的，当然除了顺序！因此可以保持在循环迭代过程中的这个性质。
（3）终止：循环全部结束后，数组已经全部排列好顺序！
