算法设计与分析——自然合并排序（分治法）

算法的C++实现以及基本思想的图解说明，参考我之前的博客

https://www.cnblogs.com/wkfvawl/p/9772447.html

合并排序是利用分治策略对n个元素进行排序的算法，其基本思想是：将待排序元素分为大小大致相同的2个子集合，分别对这两个子集合进行排序，最终将排序好的子集合合并为所要求的的排好序的集合，递归写法如下：

public static void mergeSort(Comparable []a,int left,int right)

{

if(left

{

int mid = (left + right) / 2; //取中点

mergeSort(a,left,mid); //左合并排序

mergeSort(a,mid+1,right); //右合并排序

merge(a,b,left,right); //合并到数组b

copy(a,b,left,right); //复制回数组a

}

}

其中，算法merge合并2个排序好的数组段到新的数组b中，然后由算法copy将合并后的数组段再复制回数组a中。算法merge和copy显然可以早O (n)时间内完成，因此对n个元素进行排序，最坏情况下所需要计算的时间T（n）满足

解此递归方程可知 T(n) = O(nlogn)。

按照此思想，消去递归后的合并排序可以描述为：

public static void mergeSort(Comparable []a)

{

Comparable []b = new Comparable[a.length];

int s=1;

while(s

{

mergePass(a,b,s); //合并到数组b

s+=s;

mergePass(b,a,s); //合并回数组a

s+=s;

}

}

其中，算法mergePass用于合并排好的相邻数组段。具体的合并算法由merge来实现。

public static void mergePass(Comparable []x,Comparable []y,int s)

{

int i=0;

while(i<=x.length-2*s)

{

merge(x,y,i,i+s-1,i+2*s-1);

i=i+2*s;

}

if(i+s

{

merge(x,y,i,i+s-1,x.length-1);

}

else

{

//复制到y

for(int j=i;j

{

y[j]=x[j];

}

}

}

public static void merge(Comparable[]c,Comparable[]d,int l,int m,int r)

{

int i=1;

int j=m+1;

int k=l;

while((i<==m)&&(j<=r))

{

if(c[i].compareTo(c[j])<=0) //c[i]

{

d[k++]=c[i++];

}

else //c[i]>c[j]

{

d[k++]=c[j++]

}

}

//将剩下的元素存到数组中

while(i<=m)

{

d[k++]=c[i++];

}

while(j<=r)

{

d[k++]=c[j++];

}

}

相关阅读