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.参考资料
更多推荐
Java:归并排序(合并排序)
发布评论