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

 　　2-路插入排序

　　算法思想：增加一个辅助空间d,把r[1]赋值给d[1]，并将d[1]看成是排好序后处于中间

　　位置的记录。然后从r[2]开始依次插入到d[1]之前或之后的有序序列中。

　　时间复杂度 o(n^2)

　　空间复杂度 o(1)

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

　　*/

　　void bi_insert_sort(int array[],int len)

　　{

　　int* arr_d = (int*)malloc(sizeof(int) * len);

　　arr_d[0] = array[0];

　　int head = 0,tail = 0;

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

　　{

　　if (array[i] > arr_d[0])

　　{

　　int j;

　　for ( j= tail;j>0;j--)

　　{

　　if (array[i]

　　arr_d[j+1] =arr_d[j];

　　else

　　break;

　　}

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

　　tail += 1;

　　}

　　else

　　{

　　if (head ==0)

　　{

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

　　head =len-1;

　　}

　　else

　　{

　　int j;

　　for (j = head;j arr_d[j])

　　arr_d[j-1] =arr_d[j];

　　else

　　break;

　　}

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

　　head -= 1;

　　}

　　}

　　}

　　for (int i = 0;i < len; i++)

　　{

　　int pos = (i + head );

　　if(pos >= len) pos -= len;

　　array[i] = arr_d[pos];

　　}

　　free(arr_d);

　　}

　　/*