Java教程

Java代码实现归并排序

本文主要是介绍Java代码实现归并排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

归并排序

基本思想:将初始序列中的n个对象,看成n个长度为1的有序子序列,先做两两归并,得到int(n/2)个长度为2的归并项(如果n为奇数,则最后一个有序子序列为1);在做两两归并,重复直到最后得到一个长度为n的有序序列。

图解:

图示

代码实现:

public class MergeSort{
   	//归并排序(升序)
	public static void mergeSort(int[] sorted,int left,int right){
		int min = (left + right) / 2;
		if(left < right){
			//将序列分为左右两个子序列
			//再分别对左右两个子序列再分为左右两个子序列
			mergerSort(sorted,left,min);
			mergerSort(sorted,min + 1,right);

			//排序并合并
			int[] temp = new int[right - left + 1]
			int i = left;
			int j = min + 1;
			int k = 0;
			while(i <= min && j <= right){
				if(sorted[i] < sorted[j]){
					temp[k++] = sorted[i++];
				}else{
					temp[k++] = sorted[j++];
				}
			}
			//将左边剩余的数据放入新数组
			while(i <= min){
				temp[k++] = sorted[i++];
			}
			//将右边剩余的数据放入新数组
			while(j <= right){
				temp[k++] = sorted[j++];
			}
			//排好序的新数组覆盖原数组
			for(int n = 0;n < temp.length;n++){
				sorted[n + left] = temp[n];
			}
		}
	}
	//归并排序结束
	
    //测试
    public static void main(String[] args) {
        int[] sort = new int[9];
        sort[0] = 2;
        sort[1] = 88;
        sort[2] = 1;
        sort[3] = 8;
        sort[4] = 7;
        sort[5] = 38;
        sort[6] = 28;
        sort[7] = 72;
        sort[8] = 76;
        System.out.println("Before Sort:");
        System.out.println(Arrays.toString(sort));
        MergeSort.mergerSort(sort,0,sort.length - 1);
        System.out.println("After Sort:");
        System.out.print(Arrays.toString(sort));
    }
}

运行结果:

运行结果

这篇关于Java代码实现归并排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!