归并排序使用了
归并的思想，使用的分治的策略，先把原来的数组分解为小数组，最后再慢慢将小数组合并为大数组。
归并排序的思想图解
分
1 public static void mergeSort(int[] arr) {
2 if (arr == null || arr.length < 2) {
3 return;
4 }
5 mergeSort(arr, 0, arr.length - 1);
6 }
7
8 public static void mergeSort(int[] arr, int l, int r) {
9 if (l == r) {
10 return;
11 }
12 int mid = (l + r) / 2;
13 mergeSort(arr, l ,mid);
14 mergeSort(arr, mid + 1, r);
15 merge(arr, l, mid, r);
16 }
治
1 public static void merge(int[] arr, int l , int mid, int r) {
2 // 中间数组，用于排序目标数组
3 int[] help = new int[r - l + 1];
4 // 左边数组下标
5 int i = l;
6 // 右边数组下标
7 int j = mid + 1;
8 int index = 0;
9
10 while (i <= mid && j <= r) {
11 help[index++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
12 }
13
14 while (i <= mid) {
15 help[index++] = arr[i++];
16 }
17
18 while (j <= r) {
19 help[index++] = arr[j++];
20 }
21
22 for (int k = 0; k < help.length; k++) {
23 arr[k + l] = help[k];
24 }
25 }
对数器
1 /**
2 * 对数组进行排序， 这个排序一定正确，用于验证我们编写的算法是否正确
3 * @param arr
4 */
5 public static void comparator(int[] arr) {
6 Arrays.sort(arr);
7 }
8
9 /**
10 * 随机生成不定长、不定值的数组
11 * @param maxSize 数组最大长度
12 * @param maxValue 数组最大值
13 * @return
14 */
15 public static int[] generateRandomArray(int maxSize, int maxValue) {
16 int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
17 for (int i = 0; i < arr.length; i++) {
18 arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
19 }
20 return arr;
21 }
22
23 /**
24 * 拷贝数组
25 * @param arr 需要拷贝的数组
26 * @return
27 */
28 public static int[] copyArray(int[] arr) {
29 if (arr == null) {
30 return null;
31 }
32 int[] res = new int[arr.length];
33 for (int i = 0; i < arr.length; i++) {
34 res[i] = arr[i];
35 }
36 return res;
37 }
38
39 /**
40 * 判断两个数组是否相等
41 * @param arr1 源数组
42 * @param arr2 目标数组
43 * @return
44 */
45 public static boolean isEqual(int[] arr1, int[] arr2) {
46 if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
47 return false;
48 }
49 if (arr1 == null && arr2 == null) {
50 return true;
51 }
52 if (arr1.length != arr2.length) {
53 return false;
54 }
55 for (int i = 0; i < arr1.length; i++) {
56 if (arr1[i] != arr2[i]) {
57 return false;
58 }
59 }
60 return true;
61 }
62
63 /**
64 * 输出数组结果
65 * @param arr 需要打印的数组
66 */
67 public static void printArray(int[] arr) {
68 if (arr == null) {
69 return;
70 }
71 for (int i = 0; i < arr.length; i++) {
72 System.out.print(arr[i] + " ");
73 }
74 System.out.println();
75 }
代码整合
1package com.atguigu.datastructure.baseunit1;
2
3import java.lang.reflect.Array;
4import java.util.Arrays;
5
6public class MergeSort {
7 public static void main(String[] args) {
8 int[] arr = generateRandomArray(20, 100);
9 printArray(arr);
10 mergeSort(arr);
11 printArray(arr);
12
13 }
14
15 public static void mergeSort(int[] arr) {
16 if (arr == null || arr.length < 2) {
17 return;
18 }
19 mergeSort(arr, 0, arr.length - 1);
20 }
21
22 public static void mergeSort(int[] arr, int l, int r) {
23 if (l == r) {
24 return;
25 }
26 int mid = (l + r) / 2;
27 mergeSort(arr, l ,mid);
28 mergeSort(arr, mid + 1, r);
29 merge(arr, l, mid, r);
30 }
31
32 public static void merge(int[] arr, int l , int mid, int r) {
33 // 中间数组，用于排序目标数组
34 int[] help = new int[r - l + 1];
35 // 左边数组下标
36 int i = l;
37 // 右边数组下标
38 int j = mid + 1;
39 int index = 0;
40
41 while (i <= mid && j <= r) {
42 help[index++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
43 }
44
45 while (i <= mid) {
46 help[index++] = arr[i++];
47 }
48
49 while (j <= r) {
50 help[index++] = arr[j++];
51 }
52
53 for (int k = 0; k < help.length; k++) {
54 arr[k + l] = help[k];
55 }
56 }
57
58 /**
59 * 对数组进行排序， 这个排序一定正确，用于验证我们编写的算法是否正确
60 * @param arr
61 */
62 public static void comparator(int[] arr) {
63 Arrays.sort(arr);
64 }
65
66 /**
67 * 随机生成不定长、不定值的数组
68 * @param maxSize 数组最大长度
69 * @param maxValue 数组最大值
70 * @return
71 */
72 public static int[] generateRandomArray(int maxSize, int maxValue) {
73 int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
74 for (int i = 0; i < arr.length; i++) {
75 arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
76 }
77 return arr;
78 }
79
80 /**
81 * 拷贝数组
82 * @param arr 需要拷贝的数组
83 * @return
84 */
85 public static int[] copyArray(int[] arr) {
86 if (arr == null) {
87 return null;
88 }
89 int[] res = new int[arr.length];
90 for (int i = 0; i < arr.length; i++) {
91 res[i] = arr[i];
92 }
93 return res;
94 }
95
96 /**
97 * 判断两个数组是否相等
98 * @param arr1 源数组
99 * @param arr2 目标数组
100 * @return
101 */
102 public static boolean isEqual(int[] arr1, int[] arr2) {
103 if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
104 return false;
105 }
106 if (arr1 == null && arr2 == null) {
107 return true;
108 }
109 if (arr1.length != arr2.length) {
110 return false;
111 }
112 for (int i = 0; i < arr1.length; i++) {
113 if (arr1[i] != arr2[i]) {
114 return false;
115 }
116 }
117 return true;
118 }
119
120 /**
121 * 输出数组结果
122 * @param arr 需要打印的数组
123 */
124 public static void printArray(int[] arr) {
125 if (arr == null) {
126 return;
127 }
128 for (int i = 0; i < arr.length; i++) {
129 System.out.print(arr[i] + " ");
130 }
131 System.out.println();
132 }
133
134
135}
