标签：com split 新建 ddl i++ 过程 nts compareto merge
要点：先递归向下拆分，再递归向上合并，合并后的元素是有序的，分而治之的思想。
为了理解起来简单，算法内部多了数组的创建过程。是可以优化的，可以看一下其它的归并版本。
1 public class MergeSortextends Comparable> {
2
3 private T[] sort(T[] arr, int left, int right) {
4 // 拆分中点
5 int middle = (right + left) / 2;
6 // 如果只有一个数，即左标右标相等，跳出递归
7 if (left == right) {
8 return (T[]) new Comparable[]{arr[left]};
9 }
10 printSplit(arr, left, middle);
11 // 左子列递归
12 T[] leftArr = sort(arr, left, middle);
13 printSplit(arr, middle + 1, right);
14 // 右子列递归
15 T[] rightArr = sort(arr, middle + 1, right);
16 // 合并
17 return merge(leftArr, rightArr);
18 }
19
20 private T[] merge(T[] leftArr, T[] rightArr) {
21 int lengthLeft = leftArr.length;
22 int lengthRight = rightArr.length;
23 // 左子列的游标
24 int left = 0;
25 // 右子列的游标
26 int right = 0;
27 // 新建数组的游标
28 int cur = 0;
29 // 新建放合并元素的数组
30 T[] mergeArr = (T[]) new Comparable[leftArr.length + rightArr.length];
31 // 放满了就退出
32 while (cur mergeArr.length) {
33 // 右标移动到末尾了，就把左子列的都放到数组里
34 if (right == lengthRight) {
35 while (left lengthLeft) {
36 mergeArr[cur] = leftArr[left];
37 left++;
38 cur++;
39 }
40 }
41 // 左子列的数比右子列的小，放到数组里，移动游标
42 while (left ) {
43 mergeArr[cur] = leftArr[left];
44 left++;
45 cur++;
46 }
47 // 左子列移动到末尾了，就把右子列的都放到数组里
48 if (left == lengthLeft) {
49 while (right lengthRight) {
50 mergeArr[cur] = rightArr[right];
51 right++;
52 cur++;
53 }
54 }
55 // 右子列的数比左子列的小，放到数组里，移动游标
56 while (right ) {
57 mergeArr[cur] = rightArr[right];
58 right++;
59 cur++;
60 }
61 }
62 printMerge(mergeArr);
63 return mergeArr;
64 }
65
66 private void printSplit(T[] arr, int left, int right) {
67 String[] stringArr = new String[]{" ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " "};
68 for (int i = left; i ) {
69 stringArr[i] = "*";
70 }
71 for (T n : arr) {
72 System.out.print(n);
73 }
74 System.out.println();
75 for (String s : stringArr) {
76 System.out.print(s);
77 }
78 System.out.println(" => 拆分");
79 }
80
81 private void printMerge(T[] arr) {
82 for (T n : arr) {
83 System.out.print(n);
84 }
85 System.out.print(" => 合并");
86 System.out.println();
87 }
88
89 public void sort(T[] arr) {
90 Comparable[] newArr = sort(arr, 0, arr.length - 1);
91 for (int i = 0; i ) {
92 arr[i] = (T) newArr[i];
93 }
94 }
95
96 public static void main(String[] args) {
97 Integer[] arr = new Integer[]{1, 3, 8, 7, 6, 9, 5, 4, 3, 2, 0};
98 MergeSort ms = new MergeSort();
99 ms.sort(arr);
100 }
101
102 /**
103 * 13876954320
104 * ****** => 拆分
105 * 13876954320
106 * *** => 拆分
107 * 13876954320
108 * ** => 拆分
109 * 13876954320
110 * * => 拆分
111 * 13876954320
112 * * => 拆分
113 * 13 => 合并
114 * 13876954320
115 * * => 拆分
116 * 138 => 合并
117 * 13876954320
118 * *** => 拆分
119 * 13876954320
120 * ** => 拆分
121 * 13876954320
122 * * => 拆分
123 * 13876954320
124 * * => 拆分
125 * 67 => 合并
126 * 13876954320
127 * * => 拆分
128 * 679 => 合并
129 * 136789 => 合并
130 * 13876954320
131 * ***** => 拆分
132 * 13876954320
133 * *** => 拆分
134 * 13876954320
135 * ** => 拆分
136 * 13876954320
137 * * => 拆分
138 * 13876954320
139 * * => 拆分
140 * 45 => 合并
141 * 13876954320
142 * * => 拆分
143 * 345 => 合并
144 * 13876954320
145 * ** => 拆分
146 * 13876954320
147 * * => 拆分
148 * 13876954320
149 * * => 拆分
150 * 02 => 合并
151 * 02345 => 合并
152 * 01233456789 => 合并
153 *
154 * 136789 - 02345 => 稳定性和合并过程说明
155 * ^ . ^ => []
156 * ^ . ^ => 右比左小 => [0] => 【包含赋值和移动，下同】
157 * ^ . ^ => 左比右小 => [0, 1]
158 * ^ . ^ => 右比左小 => [0, 1, 2]
159 * ^ . ^ => 左右相等，左侧含等号，右侧不含，跳过 => [0, 1, 2]
160 * ^ . ^ => 左右相等，进入 => [0, 1, 2, 3]
161 * ^ . ^ => 右比左小 => [0, 1, 2, 3, 3] => 顺序未改变，稳定
162 * ^ . ^ => 右比左小 => [0, 1, 2, 3, 3, 4]
163 * ^ . ^=> 右比左小 => [0, 1, 2, 3, 3, 4, 5] => 右标 = 右子列长度
164 * ^ . => 左子列剩余元素移入数组 => [0, 1, 2, 3, 3, 4, 5, 6]
165 * ^ . => 左子列剩余元素移入数组 => [0, 1, 2, 3, 3, 4, 5, 6, 7]
166 * ^ . => 左子列剩余元素移入数组 => [0, 1, 2, 3, 3, 4, 5, 6, 7, 8]
167 * ^. => 左子列剩余元素移入数组 => [0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9] => 左标 = 左子列长度
168 * 游标cur = 数组长度，退出循环，完成合并过程
169 *
170 * 每层遍历一遍，遍历了logn次
171 * => 遍历次数：nlogn
172 * => 时间复杂度：O(nlogn)
173 * => 稳定性：稳定
174 *
175 */
176
177 }
算法 - 归并排序
标签：com split 新建 ddl i++ 过程 nts compareto merge
原文地址：https://www.cnblogs.com/SamNicole1809/p/12793829.html