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

　　归并排序

　　算法思想：设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。

　　时间复杂度 o(nlogn)

　　空间复杂度 o(n)

　　比较次数 ?

　　*/

　　void merge(int array[],int i,int m, int n)

　　{

　　int j, k;

　　int iStart = i, iEnd = n;

　　int arrayDest[256];

　　for ( j = m + 1,k = i; i <= m&& j <= n; ++k)

　　{

　　if (array[i] < array[j])

　　arrayDest[k] = array[i++];

　　else

　　arrayDest[k] = array[j++];

　　}

　　if (i <= m)

　　for (;k <= n; k++,i++)

　　arrayDest[k] = array[i];

　　if(j <= n)

　　for (;k <= n; k++,j++)

　　arrayDest[k] = array[j];

　　for(j = iStart; j <= iEnd; j++)

　　array[j] = arrayDest[j];

　　}

　　void merge_sort(int array[],int s,int t)

　　{

　　int m;

　　if (s < t)

　　{

　　m = (s + t )/2;

　　merge_sort(array,s,m);

　　merge_sort(array,m+1,t);

　　merge(array,s,m,t);

　　}

　　}

　　/*

　　软考程序员考试历年真题重点题总结及答案

　　2011年上半年软考报名时间及方式汇总

　　软考程序员考试历年真题汇总(2007年-2010年)