常见内部排序算法之归并排序_JAVA_编程开发_程序员俱乐部

常见内部排序算法之归并排序
来自百度百科的解释：
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的（一开始每个子序列只有一个，也是有序）。然后再把有序子序列合并为整体有序序列。
算法描述：
归并操作的过程如下：
    申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
    设定两个指针，最初位置分别为两个已经排序序列的起始位置
    比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
    重复步骤3直到某一指针达到序列尾
    将另一序列剩下的所有元素直接复制到合并序列尾
还是图解比较有说服力：网上找的图

下面是源代码：纯属个人理解，如有错误，欢迎指正！

class="java" name="code">
package test.aglorith;

import java.util.Arrays;

public class MergeSort{
	public static void sort(int[] data){
		int data_len=data.length;
		int group=1;
		while(group<=data_len){
			for(int i=0;i<data_len-1;i=i+group*2){
				merge(data,i,group);
			}
			System.out.println(Arrays.toString(data)+"--每几个为一组--"+group);
			group=2*group;
		}
	}
	public static void merge(int[] data,int i,int group){
		int j=i+group;//设置右边是移动指针
		int count1=group;//左边数组元素个数
		int count2=group;
		//出现单个分组，即不用管
		if(data.length-j<0){
			return;
		}
		//可能会出现右边数组相对比较少，例如：最后两组，一组四个，一组三个
		if(data.length-j<group){
			count2=data.length-j;
		}
		//定义一个备用数组
		int temp_size=count1+count2;
		int[] temp=new int[temp_size];
		int k=0;//备用数组还剩多少空闲
		//迁移到备用数组
		while(i<j&&count1>0&&count2>0){
			if(data[i]<=data[j]){temp[k]=data[i];i++;count1--;}
			else{temp[k]=data[j];j++;count2--;}
			k++;
		}
		if(count1==0){while(k<temp_size){temp[k]=data[j];k++;j++;}}
		if(count2==0){while(k<temp_size){temp[k]=data[i];k++;i++;}}
		//把备用数组的有序数组迁回原数组
		int n=temp_size;
		while (n>0) {
			j--;n--;
			data[j]=temp[n];
		}
	}
	public static void main(String[] args){
		int[] data=new int[]{10,9,8,7,6,5,4,3,2,1};
		System.out.println("排序之前");
		System.out.println(Arrays.toString(data));
		System.out.println("------------");
		sort(data);
	}
}

• 
• 大小: 22.4 KB

• 查看图片附件