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

　　歸并排序

　　算法思想：設(shè)兩個(gè)有序的子文件(相當(dāng)于輸入堆)放在同一向量中相鄰的位置上：R[low..m]，R[m+1..high]，先將它們合并到一個(gè)局部的暫存向量R1(相當(dāng)于輸出堆)中，待合并完成后將R1復(fù)制回R[low..high]中。

　　時(shí)間復(fù)雜度 o(nlogn)

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

　　比較次數(shù) ?

　　*/

　　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);

　　}

　　}

　　/*

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

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

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