JAVA实现归并排序_归并排序java实现

 一.摘要:

        归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

原理:

• 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
• 解决（Conquer）：用合并排序法对两个子序列递归的排序。
• 合并（Combine）：合并两个已排序的子序列已得到排序结果。

二.步骤:

1.归并函数-函数入口:

public static void merge(long[] arry) //arry为需要排序的数组
    
{
 
		int n=arry.length;//得到数组的长度
		
        long[] temArr = new long[n];//生成一个临时数组
			
        mergeDiv(arry,temArr,0,n-1);//1.分解
     
}

2.归并函数-数组分组:(分解)

private static void mergeDiv(long[] arr,long[] temArr,int right,int left) 
{
		
        if(right<left)//当前组中数字个数大于1时
		{
			int mid = (right+left)/2;//数组中间的位置
 
			mergeDiv(arr,temArr,right,mid);//分解:将数组左半边的数字分为一组
 
	 		mergeDiv(arr,temArr,mid+1,left);//分解:将数组右半边的数字分为一组
 
	        mergeSort(arr,temArr,right,mid,left);//解决：对分解的数组进行排序、合并
		}
 
	}

3.归并函数-数组排序、合并:

private static void mergeSort(long[] arry,long[] temArr,int left ,int mid,int right)
	{
		//对分解的数组进行排序、合并
		int leftPos=left;//左边一组，第一个数字的位置下标
		
        int rightPos=mid+1;//右边一组，第一个数字的位置下标
		
        int pos=left;//临时存储数组开始存放时的初始下标
		
        while(leftPos<=mid&rightPos<=right)
		{
			if(arry[rightPos]<arry[leftPos])
			{
				temArr[pos++]=arry[rightPos++];
			}else {
				temArr[pos++]=arry[leftPos++];
			}
		}
		
		while(leftPos<=mid)//将左边一组组内多余数字存入临时数组
		{
			temArr[pos++]=arry[leftPos++];
		}
		
		while(rightPos<=right)//将右边一组组内多余数字存入临时数组
		{
			temArr[pos++]=arry[rightPos++];
		}
		
		while(left<=right)//将临时数组内排序号的数字存入数组
		{
			arry[left]=temArr[left];
			left++;
		}
	}

三.原代码及测试结果:

1.源代码:

final class newSort {
	
	private newSort(){}
	
	public static void showArry(long[] arry){
		for(long m : arry) {System.out.printf("%d ", m);}System.out.println();}
	
	//排序1调用入口:
	public static void merge(long[] arry){
			int n=arry.length;
		long[] temArr = new long[n];
			mergeDiv(arry,temArr,0,n-1);}
	
	private static void mergeDiv(long[] arr,long[] temArr,int right,int left) {
		if(right<left)
		{
			int mid = (right+left)/2;
			mergeDiv(arr,temArr,right,mid);
	 		mergeDiv(arr,temArr,mid+1,left);
			mergeSort(arr,temArr,right,mid,left);
		}
	}
	
	private static void mergeSort(long[] arry,long[] temArr,int left ,int mid,int right)
	{
		
		int leftPos=left;
		int rightPos=mid+1;
		int pos=left;
		while(leftPos<=mid&rightPos<=right)
		{
			if(arry[rightPos]<arry[leftPos])
			{
				temArr[pos++]=arry[rightPos++];
			}else {
				temArr[pos++]=arry[leftPos++];
			}
		}
		
		while(leftPos<=mid)
		{
			temArr[pos++]=arry[leftPos++];
		}
		
		while(rightPos<=right)
		{
			temArr[pos++]=arry[rightPos++];
		}
		
		while(left<=right)
		{
			arry[left]=temArr[left];
			left++;
		}
	}
	/************************归并排序**************************/
	
}

public class Test {
 
	public static void main(String[] args)
	{
		long[] arry= {3,1,9,2,5,7,4,6,8,11,10};
	
		System.out.println("未排序:");
			newSort.showArry(arry);
	
		System.out.println("排序后:");
			newSort.merge(arry);
			newSort.showArry(arry);
		
	}
	
}

2.测试结果:

未排序:
3 1 9 2 5 7 4 6 8 11 10 
排序后:
1 2 3 4 5 6 7 8 9 10 11