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

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个元素是有序的。该算法设计的方法是增量方法
1 void insert_sort(int *datas,int length)
2 {
3 int i,j;
4 int key,tmp;
5 //判断参数是否合法
6 if(NULL == datas || 0==length)
7 {
8 printf("Check datas or length.\n");
9 exit(1);
10 }
11 //数组下标是从0开始的，从第二个元素（对应下标1）开始向前插入
12 for(j=1;j<length;j++)
13 {
14 key = datas[j]; //记录当前要插入的元素
15 i = j-1; //前面已经有序的元素
16 //寻找待插入元素的位置，从小到到排序，如果是从大到小改为datas[i]<key
17 while(i>=0 && datas[i] > key)
18 {
19 /×tmp = datas[i+1];
20 datas[i+1] = datas[i];
21 datas[i] = tmp;×/ 这个过程不需要进行交换，因为要插入的值保存在key中，没有被覆盖掉，在此感谢”两生花“指出问题所在
datas[i+1] = datas[i];
22 i--; //向前移动
23 }
24 datas[i+1] = key; //最终确定待插入元素的位置
25 }
26 }
插入排序算法的分析

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