UC知道JAVA 归并算法
来源：百度知道 编辑：UC知道 时间：2024/07/03 00:14:42
public class Mergesort {
public static void sort(int[] a)
{
if(a.length > 2)
{
int halfLength = a.length/2;
int[] front = new int[halfLength];
int[] tail = new int[a.length-halfLength];
divide(a, front, tail);
sort(front);
sort(tail);
merge(a,front,tail);
}
}
private static void divide(int[] a,int[] front, int[] tail)
{
int i;
for(i=0;i<front.length;i++)
front[i] = a[i];
for(i=0;i<tail.length;i++)
tail[i] = a[front.length+i];
}
private static void merge(int[] a,int[] front, int[] tail)
{
int frontIndex = 0, tailIndex = 0,aIndex =0;
while((frontIndex<front.length)&&(tailIndex<tail.length))
{
if(front[frontIndex]<tail[tailIndex]){
a[aIndex] = front[frontIndex];
aIndex++;
frontIndex++;}
else
{
a[aIndex] = tail[tail
public static void sort(int[] a)
{
if(a.length > 2)
{
int halfLength = a.length/2;
int[] front = new int[halfLength];
int[] tail = new int[a.length-halfLength];
divide(a, front, tail);
sort(front);
sort(tail);
merge(a,front,tail);
}
}
private static void divide(int[] a,int[] front, int[] tail)
{
int i;
for(i=0;i<front.length;i++)
front[i] = a[i];
for(i=0;i<tail.length;i++)
tail[i] = a[front.length+i];
}
private static void merge(int[] a,int[] front, int[] tail)
{
int frontIndex = 0, tailIndex = 0,aIndex =0;
while((frontIndex<front.length)&&(tailIndex<tail.length))
{
if(front[frontIndex]<tail[tailIndex]){
a[aIndex] = front[frontIndex];
aIndex++;
frontIndex++;}
else
{
a[aIndex] = tail[tail
例子 97，48，12，56，37，88，26，76
第一次分为 a1:97，48，12，56 a2:37，88，26，76
没有排序，因为有迭代sort(tail)方法，
第二次分为 a1:97,48 a2=12,56 a3:37,88 a4=26,76
这个时候开始排序
变成 a1:48,97 a2=12,56 a3:37,88 a4=26,76
数组合并 a1:12,48,56,97 a2:26,37,76,88
数组再合并 a:12,26,37,48,56,76,88,97
得到结果
对，是递归算法，楼主可以以实例化来理解。