2011年軟考程序員考試復習筆試知識點整理(5)

　　希爾排序

　　算法思想：先將整個待排序記錄分割成若干子序列分別進行直接插入排

　　序，待整個序列中的記錄基本有序時，再對全體記錄進行一

　　次直接插入排序

　　時間復雜度 o(n^2)

　　空間復雜度 o(1)

　　比較次數 ?

　　*/

　　void shell_insert(int array[],int d,int len)

　　{

　　int tmp,j;

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

　　{

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

　　{

　　tmp = array[i];

　　j = i - d;

　　do

　　{

　　array[j+d] = array[j];

　　j = j - d;

　　} while (j >= 0 &&tmp < array[j]);

　　array[j+d] = tmp;

　　}

　　}

　　}

　　void shell_sort(int array[],int len)

　　{

　　int inc = len;

　　do

　　{

　　inc = inc/2;

　　shell_insert(array,inc,len);

　　} while (inc > 1);

　　}

　　/*

　　軟考程序員考試歷年真題重點題總結及答案

　　2011年上半年軟考報名時間及方式匯總

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