2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理(5)

　　2-路插入排序

　　算法思想：增加一個(gè)輔助空間d,把r[1]賦值給d[1]，并將d[1]看成是排好序后處于中間

　　位置的記錄。然后從r[2]開(kāi)始依次插入到d[1]之前或之后的有序序列中。

　　時(shí)間復(fù)雜度 o(n^2)

　　空間復(fù)雜度 o(1)

　　比較次數(shù) 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 <=len-1;j++)

　　{

　　if (array[i] >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);

　　}

　　/*

　　軟考程序員考試歷年真題重點(diǎn)題總結(jié)及答案

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)