2011年软考程序员考试复习笔试知识点整理(5)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);

　　}

　　/*