【数据结构】【排序】归并排序

顾名思义，归并排序的核心思想就是“归并”，将两个有序的数列进行“二路归并”能够非常快速的实现合并成一个有序数列：

public static void mergeArray(int[] array,int[] temp,int low,int midLoc,int high){
		int i=low;
		int j=midLoc+1;
		int k=0;
		while(i<=midLoc&&j<=high){
			if(array[i]<array[j]){
				temp[k++]=array[i];
				i++;
			}else{
				temp[k++]=array[j];
				j++;
			}
		}
		while(i<=midLoc){
			temp[k++]=array[i];
			i++;
		}
		while(j<=high){
			temp[k++]=array[j];
			j++;
		}
		for(i=0;i<k;i++){
			array[i+low]=temp[i];
		}
	}

 使用这种思想，可以递归的将一个无序的数列切割成一个个的小子数列，直到最小长度1，然后两两之间进行归并，最终就能够实现数列的整体有序了：

import java.util.Scanner;

public class MergeSort{
	public static void main(String args[]){
		Scanner scanner=new Scanner(System.in);
		int total=scanner.nextInt();
		int[] array=new int[1024];
		for(int i=0;i<total;i++){
			array[i]=scanner.nextInt();
		}
		//这里定义一个临时数组以提高效率（只定义这一个）
		int temp[]=new int[1024];
		mergeSort(array,0,total-1,temp);
		output(array,total);
	}
	public static void output(int[] array,int total){
		for(int i=0;i<total;i++){
			System.out.print(array[i] +" ");
		}	
		System.out.println();
	}
	
	public static void mergeSort(int[] array,int low,int high,int[] temp){
		if(low<high){
			int midLoc=(low+high)/2;
			mergeSort(array,low,midLoc,temp);	
			mergeSort(array,midLoc+1,high,temp);
			mergeArray(array,temp,low,midLoc,high);
		}
	}
	public static void mergeArray(int[] array,int[] temp,int low,int midLoc,int high){
		int i=low;
		int j=midLoc+1;
		int k=0;
		while(i<=midLoc&&j<=high){
			if(array[i]<array[j]){
				temp[k++]=array[i];
				i++;
			}else{
				temp[k++]=array[j];
				j++;
			}
		}
		while(i<=midLoc){
			temp[k++]=array[i];
			i++;
		}
		while(j<=high){
			temp[k++]=array[j];
			j++;
		}
		for(i=0;i<k;i++){
			array[i+low]=temp[i];
		}
	}
}

 输入N个数作为数组的长度，然后输入N个无序的整数，回车即可查看排序的结果：

写道

输入：

10

1 4 7 2 5 8 3 6 9 0

输出：

0 1 2 3 4 5 6 7 8 9