Java:归并排序（合并排序）

Java:归并排序（合并排序）"/>

Java:归并排序（合并排序）

1.合并排序

1.1 什么是分治法？
分治法就是分而治之,大问题一时半会解决不了，但是可以把大问题拆分成几个小问题，小问题解决了，大问题不就解决了。

• 分–将问题分解为规模更小的子问题
• 治–将这些规模更小的子问题逐个击破
• 合–将已解决的子问题合并，最终得出“母”问题的解

1.2 合并排序
合并排序完全符合分治法的实现模式：

• 分–将待排序数组分成两个待排序的子序列
• 治–使用递归排序两个子序列
• 合–合并已排序的子序列，就可以得到整个数组已排序的结果

2.合并排序动图

3.Java代码

import java.util.Arrays;public class mergeSort {public static void main(String[] args) {int[] arr = {3,41,52,26,38,57,9,49};System.out.println("未排序的数组："+Arrays.toString(arr));mergeSort(arr);System.out.println("排序后的数组："+Arrays.toString(arr));}/** 对数组进行划分,分到不能再分为止* */private static int[] mergeSort(int[] arr) {//当数组长度为1时,递归回升if (arr.length<=1){return arr;}int mid = arr.length/2;int[] left = Arrays.copyOfRange(arr,0,mid);int[] right = Arrays.copyOfRange(arr,mid,arr.length);return merge(arr, mergeSort(left), mergeSort(right));}/** 进行合并* */private static int[] merge(int[] arr, int[] left, int[] right) {//left数组的下标int i = 0;//right数组的下标int j = 0;for (int index = 0; index < arr.length; index++) {//注意一下，数组越界问题//i>=left.length时,将right数组的值给arrif (i>=left.length){arr[index]=right[j++];}else if(j>=right.length){arr[index]=left[i++];}else if (left[i]<right[j]){//left[i]<right[j]时,将left数组的值给arr,小的优先给arrarr[index]=left[i++];}else {arr[index]=right[j++];}}return arr;}
}

4.参考资料