Question

java编程合并排序算法

代码如下，不知何故，排出的结果不对，求高人指点（个人估计还是merge函数不对）
public static void main(String[] args)
{
Integer arr[]={25,2,4,13,6};
Integer tmpArry[]=new Integer[5];
Mergesort mg=new Mergesort();
mg.mergesort(arr, tmpArry, 0, 4);//len-1);
mg.show(tmpArry);
}
class Mergesort
{

public <T extends Comparable<? super T>>
void mergesort(T[] a,T[]tmpArry,int left,int right)
{
if(left<right)
{
int center=(left+right)/2;
mergesort(a,tmpArry,left,center);
mergesort(a,tmpArry,center+1,right);
merge(a,tmpArry,left,center+1,right);
}
}
}

public <T extends Comparable<? super T>>
void merge(T[] a,T[]tmpArry,int leftPos,int rightPos,int rightEnd)
{
int leftEnd=rightPos-1;
int tmpPos=leftPos;
//int numElements=rightEnd-leftPos+1;

while(leftPos <=leftEnd && rightPos <=rightEnd)
{
if(a[leftPos].compareTo(a[rightPos])<=0)
{
tmpArry[tmpPos++]=a[leftPos++];
}else{
tmpArry[tmpPos++]=a[rightPos++];
}
}
while(leftPos<=leftEnd)
{
tmpArry[tmpPos++]=a[leftPos++];
}
while(rightPos<=rightEnd)
{
tmpArry[tmpPos++]=a[rightPos++];
}

}
public <T extends Comparable<? super T>>
void show(T tmpArry[])
{
for(int i=0;i<tmpArry.length;i++){
System.out.println("after Mergesort the tmpArry"+i+" is"+tmpArry[i]);
}
}

}

Answer 1

package p1;

import java.util.Arrays;

public class Guy
{
	/**
	 * 归并排序
	 */
	private static void mergeSort ( int[] array, int start, int end, int[] tempArray )
	{
		if (end <= start)
		{
			return;
		}
		int middle = ( start + end ) / 2;
		mergeSort (array, start, middle, tempArray);
		mergeSort (array, middle + 1, end, tempArray);
		int k = 0, leftIndex = 0, rightIndex = end - start;
		System.arraycopy (array, start, tempArray, 0, middle - start + 1);
		for ( int i = 0; i < end - middle; i++ )
		{
			tempArray[end - start - i] = array[middle + i + 1];
		}
		while (k < end - start + 1)
		{
			if (tempArray[rightIndex] > tempArray[leftIndex]) // 从小到大
			{
				array[k + start] = tempArray[leftIndex++];
			}
			else
			{
				array[k + start] = tempArray[rightIndex--];
			}
			k++;
		}
	}

	public static void main ( String[] args )
	{
		int[] array = new int[] { 11, 213, 134, 65, 77, 78, 23, 43 };
		mergeSort (array, 0, array.length - 1, new int[array.length]);
		System.out.println (Arrays.toString (array));
	}
}

追问

你的代码写的很好，能不能麻烦修改下我的代码，我想了好久也没发现问题所在

追答

你的方法好多啊，我看不太懂啊