MergeSort归并排序图文代码详解

MergeSort归并排序就是将一组数分割成两个子数组，再对子数组进行排序，然后再归并起来。

在这个过程中，通过递归的方式对子数组进行归并排序。

过程（Wikipedia）：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

废话不多说，上图：

代码如下：

<span style="font-size:18px;">import java.util.Arrays;


public class MergeSort {
	public static void mergeSort(int [] array){
		 
		int middle=array.length/2;//中间标
		 
		if(array.length>1){
		 
		int[]left=Arrays.copyOfRange(array,0,middle);//拷贝数组array的左半部分
		int[]right=Arrays.copyOfRange(array,middle,array.length);//拷贝数组array的右半部分
		mergeSort(left);//对左边数组递归
		mergeSort(right);//对右边数组递归
		merge(array,left,right);//数组左、右合并到Array
		 
		 for (int j = 0; j < array.length; j++) {
             System.out.print(array[j]);
             System.out.print(",");
         }
         System.out.println();
		}
		}
		 
		//合并数组，升序
		private static void merge(int[]result,int[]left,int[]right){
		 
		int i=0,l=0,r=0;
		 
		while(l<left.length&&r<right.length){
		 
		if(left[l]<right[r]){
		result[i]=left[l];
		i++;
		l++;
		}else{
		result[i]=right[r];
		i++;
		r++;
		}
		}
		//如果右边剩下合并右边的
		while(r<right.length){
		result[i]=right[r];
		r++;
		i++;
		}
		//如果左边剩下合并左边的
		while(l<left.length){
		result[i]=left[l];
		l++;
		i++;
		}
		}

		public static void main(String[] args) {
	        int[] arr = { 55, 56, 23, 90, 47, 9, 40, 82, 76, 33 };
	        for (int i = 0; i < arr.length; i++) {
	            System.out.print(arr[i]);
	            System.out.print(",");
	        }
	        System.out.println();
	        mergeSort(arr);
	    }
}
</span>
           

结果：

可以看出，对数组进行分割排序的过程。