典范排序--合并排序

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）继承实行向左向右拆分，以保证数组与其他数组举行兼并前内部有序。