本篇内容:
算法思想:
将两个或两个以上的有序表合并成一个新的有序表,
即把待排序序列分成若干个子序列,每个子序列是有序的,然后在把有序子序列合并为整体有序序列.
此算法分为两步:
(1)把数组等长切分;
(2)把切分后的数组进行排序,然后合并;
通过切分方法的递归调用,可以将数组切分到最小(2个元素)的组合;
代码:
(1)合并两个数组的方法:
//将两个数组合并
public static void Merge(int[] array,int low,int mid,int high)
{
int[] temp = new int[high-low+1];
int pLeft = low;
int pRight = mid+1;
int k = 0;
//先把较小的数移到新数组中
while(pLeft <= mid&&pRight <= high)
{
if(array[pLeft]<array[pRight])
{
temp[k++] = array[pLeft++];
}else
{
temp[k++] = array[pRight++];
}
}
//把左边剩余的数移到新数组中
while(pLeft <= mid)
{
temp[k++] = array[pLeft++];
}
//把右边剩余的数移入新数组
while(pRight <= high)
{
temp[k++] = array[pRight++];
}
//用新数组中的数覆盖array数组
for(int i = 0;i < temp.length ; i++)
{
array[i+low] = temp[i];
}
printArray(array);
}
(2)自顶向下合并数组
/*
* 将两个或两个以上的有序表合并成一个新的有序表
* 即把待排序序列分成若干个子序列,每个子序列是有序的,然后在把有序子序列合并为整体有序序列
* */
public static void MergeSorting(int[] array,int low,int high)
{
if(low == high)
{
return;
}
int mid = (low + high)/2;
if(low<high)
{
//对左边排序
MergeSorting(array,low,mid);
//对右边排序
MergeSorting(array,mid+1,high);
//左右合并
Merge(array,low,mid,high);
}
}
实现结果: