典范排序--合并排序
2019-11-18杂谈搜奇网47°c
A+ A-兼并排序的道理
兼并排序是应用兼并的头脑完成的排序要领,该要领采纳典范的分治战略(分治法将题目分红一些小的题目然后递归求解,而治的阶段则是将分的阶段获得的答案修补在一起,即分而治之)。
图解兼并排序
下面我们以待排序数组 8,4,5,7,1,3,6,2,9,10为例,以图解的体式格局解说兼并排序的道理。
(1)分治道理图(因为图片太大,没法截全,我举行了肯定紧缩,所以看起来有点新鲜...)
从图中能够看出,兼并排序是先将数组举行拆分,拆分到盈余一个关键字,这是一个从大到小的历程。然后再举行治理,治理的历程也就是举行兼并的历程,兼并时会保证摆布双方的数组内部各自有序。然后将两个有序的数组兼并到一个数组中,且兼并后的数组有序。总结就是:递归拆分,回溯兼并,兼并时摆布两个数组内部有序。
(2)递归道理图
在看递归道理图前,我们先看下兼并排序的代码,以下所示
1 public class MergeSort { 2 private static int count = 1; 3 public static void main(String[] args) { 4 int[] arr = {8, 4, 5, 7, 1, 3, 6, 2, 9, 10}; 5 int[] temp = new int[arr.length]; 6 split(arr, 0, arr.length - 1, temp); 7 System.out.println(Arrays.toString(arr)); 8 } 9 10 /** 11 * 递归拆分数组然后兼并 12 * 13 * @param arr 待拆分数组 14 * @param left 数组左侧下标 15 * @param right 数组右下标 16 * @param temp 用于寄存兼并后的有序序列的数组 17 */ 18 public static void split(int[] arr, int left, int right, int[] temp) { 19 if (left >= right) { 20 return; 21 } 22 System.out.println("拆分第"+(count++)+"次"); 23 int mid = left + (right - left) / 2; 24 //向左拆分 25 split(arr, left, mid, temp); 26 //向右拆分 27 split(arr, mid + 1, right, temp); 28 //每次拆分后都实行兼并 29 merge(arr, left, mid, right, temp); 30 } 31 32 /** 33 * 兼并两个各自有序序列(以mid为界) 34 * 35 * @param arr 原始数组 36 * @param left 数组左侧下标 37 * @param mid 数组中心下标 38 * @param right 数组右侧下标 39 * @param temp 用于寄存新的有序数组 40 */ 41 public static void merge(int[] arr, int left, int mid, int right, int[] temp) { 42 int i = left; 43 int j = mid + 1; 44 //temp中的原始下标 45 int t = 0; 46 47 while (i <= mid && j <= right) { 48 //双方数组都没有比较完 继承 49 if (arr[i] < arr[j]) { 50 //左侧数组中值更小 51 temp[t] = arr[i]; 52 i++; 53 } else { 54 //右侧数组中值更小 55 temp[t] = arr[j]; 56 j++; 57 } 58 t++; 59 } 60 //有一边已悉数复制到temp中了 61 if (i <= mid) { 62 //左侧还没有复制完,将左侧悉数元素复制到temp中 63 while (i <= mid) { 64 temp[t] = arr[i]; 65 i++; 66 t++; 67 } 68 } else if (j <= right) { 69 //右侧还没有复制完,将右侧悉数元素复制到temp中 70 while (j <= right) { 71 temp[t] = arr[j]; 72 j++; 73 t++; 74 } 75 } 76 //将temp复制到原arr中 77 t = 0; 78 while (left <= right) { 79 arr[left] = temp[t]; 80 left++; 81 t++; 82 } 83 } 84 }
我们都晓得在jvm内存模子中,线程每挪用一个要领就会将该要领压入本线程的栈中。在递归要领的挪用历程当中也是云云,只不过每次压栈的要领名都雷同,这里我们为了好辨别递归实行到哪一层,工资的为递归要领编号,即每递归一次编号加1。如上图所示,数组8,4,5,7,1,3,6,2,9,10第一次拆分时,left = 0,right=9,mid=4 (三者均示意下标),然后继承向左递归拆分即split1要领入栈,此时left=0,right=4,mid=2。然后继承向左递归拆分。。。。直到left=right即只剩下一个数字没法再拆分,即我们上图中的split4,所以split4要领出栈回溯到要领split3中,split3代码向下实行,实行向右递归拆分,这里我们为了轻易辨别,将向右递归的历程又画了一个栈来示意,即上图中心的栈图,此时向右递归的split0入栈,此时left=right=1,split0出栈,split3继承向下实行,即实行merge兼并要领,此时兼并要领参数left=0,right=1,mid=0,即8和4两个离别有序的数组举行兼并(单个数字内部固然有序)。
merge要领实行完后,split3递归要领实行终了,出栈,回溯到递归要领split2中,继承实行上述步骤。须要申明的是,上述历程在向右递归时因为mid背面只要一个数字4,所以left=right=1,所以向右递归要领直接出栈,而在向左递归实行到split1时,mid背面有两个数字7,1所以在向右递归时会将当前数组(7,1)继承实行向左向右拆分,以保证数组与其他数组举行兼并前内部有序。
(3)兼并图解
下面以末了一次兼并为例,图解兼并的实行历程。即1,4,5,7,8与2,3,6,9,10两个有序数组的兼并历程
(4)总结
以上就是兼并排序的实行道理,重要分为以下步骤:
1.递归的体式格局举行拆分,将大的数组拆分红小的数组,直到盈余一个不能拆分
2.回溯的时刻举行兼并,兼并时以mid为界,摆布双方各自有序,经由过程分外的空间temp数组,将两个有序数组兼并到一个有序数组中
3.将兼并后的数组复制到原数组中,当回溯完成时全部数组有序