Java之归并排序

归并排序

归并排序(Merge Sort)算法，使用的是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

核心源码: mergeSort(m->n) = merge(mergeSort(m->k),mergeSort(k+1->n))；

算法思路：

​ 如果要排序一个数组，先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。具体见下图：

注意：分治思想跟递归思想很相似。分治是一种解决问题的处理思想，递归是一种编程技巧，这两者并不冲突，分治算法一般都是用递归来实现。

具体代码实现如下：

import java.util.Arrays; import org.junit.Test;  /**  *  * @ClassName: MergeSort * @author shaoyb * @date 2020年12月9日 * @Description: 归并排序 * 归并排序思路： *	1、把长度为n的序列一分为二成两个子序列； 	2、对这两个子序列分别采用归并排序； 	3、将两个排序好的子序列合并成一个最终的排序序列。  */ public class MergeSort { 	 	/** 	 * 归并排序算法实现 	 * @param arr 需要排序的数组 	 * @return 排序成功后新数组 	 */ 	public int[] mergeSort(int[] arr){ 		//1.确定递归终止条件 		if(arr.length < 2) { 			return arr; 		} 		 		//2.拆解数组成左右两部分 		int mid = arr.length/2; 		int[] left = Arrays.copyOfRange(arr,0,mid); 		int[] right = Arrays.copyOfRange(arr,mid,arr.length); 		 		//3.对拆解后两个数组进行合并 		return merge(mergeSort(left),mergeSort(right)); 	} 	 	/** 	* 合并两个有序数组，并返回合并后的新数组 	* @param left 	* @param right 	*/ 	public int[] merge(int[] left,int[] right) { 		//1.定义好新数组 		int[] newArray = new int[left.length + right.length]; 		 		//2.往新数组中逐个添加元素 		int lIndex = 0; 		int rIndex = 0; 		for(int i = 0; i < newArray.length; i++) { 			if(lIndex >= left.length) { 				//左数组已经遍历完成 				newArray[i] = right[rIndex++]; 			}else if(rIndex >= right.length) { 				//右数组已经遍历完成 				newArray[i] = left[lIndex++]; 			}else if(left[lIndex] < right[rIndex]) { 				//左数组当前元素值小于右数组 				newArray[i] = left[lIndex++]; 			}else { 				//右数组当前元素值小于左数组 				newArray[i] = right[rIndex++]; 			} 		} 		 		return newArray; 	} 		 	@Test 	public void testMergeSort(){ 		//1.定义数组 		int[] array = new int[] {5,2,6,9,0,3}; 		 		System.out.println("排序前" + Arrays.toString(array)); 		 		//2.归并排序 		array = mergeSort(array); 		 		System.out.println("排序后" + Arrays.toString(array)); 	}	 }