插入排序是算导第一个分析的算法。

之前看了很多遍，一直没有把习题做了，现在好好把习题和思考题做做，锻炼自己能力，顺便用C语言实现经典算法和数据结构。

 最基础的插入排序是对前n-1项数据进行反向扫描。实现很简单，运行时间也很容易的出，直接贴代码：

void insertion_sort(int A[], int length){    int i, j;    int key;    for(j = 1; j < length; j++)    {        key = A[j];        i = j - 1;        while(i >= 0 && A[i] > key)        {            A[i+1] = A[i];            i--;        }        A[i+1] = key;    }}

 

练习题2.3-4要求将插入排序改写成递归过程。实现也是比较简单。

 

void insertion(int A[], int length){    if(length != 1){        int key = A[length-1];        int i = length-2;        while(i >= 0 && A[i] > key){            A[i+1] = A[i];            i--;        }        A[i+1] = key;    }}void insertion_sort(int A[], int length){    if(length > 1){        insertion_sort(A, length-1);        insertion(A, length);    }}

 

 

 练习2.3-6要求将最基础版本中的线性查找策略改成二分查找。

  

int binary_search(int A[], int key, int end){     int i = 0;     int j = end;     int m;     while(i < j){        m = (i + j) / 2;        if(key > A[m]){            i = m + 1;        }        else{            j = m;        }     }     if(A[i] >= key)         return i;     else         return i + 1;}void insertion_sort(int A[], int length){    int i, j;    int key;    int pos;    for(j = 1; j < length; j++)    {        key = A[j];        pos = binary_search(A, key, j-1);        for(i = j-1; i >= pos; i--)            A[i+1] = A[i];        A[pos] = key;    }}