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

 归并排序

　　算法思想：设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：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