2011年软考程序员考试复习笔试知识点整理(5)3

 　直接插入排序

　　算法思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元

　　素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它

　　插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

　　时间复杂度 o(n^2)

　　空间复杂度 o(1)

　　比较次数 n(n+1)/2

　　*/

　　void insert_sort(int array[],int len)

　　{

　　int tmp,i,j;

　　for(i = 1;i < len;i++)

　　{

　　if (array[i] < array[i-1])

　　{

　　tmp = array[i];

　　array[i] = array[i-1];

　　//插入到相应位置

　　for (j = i-2;j >= 0;j--)

　　{

　　//往后移

　　if (array[j] > tmp)

　　array[j+1] =array[j];

　　else

　　{

　　array[j+1] = tmp;

　　break;

　　}

　　}

　　if(j == -1)

　　array[j+1] = tmp;

　　}

　　}

　　}

　　/*