MergeSort归并排序（罗召勇版）

1 package mergesort;
2
3 import java.util.Arrays;
4
5 public class MergeSort {
6 public static void main(String[] args) {
7 int[] arr = new int[]{11, 6, 22, 2, 21, 19, 3, 8, 24, 31};
8 System.out.println(Arrays.toString(arr));
9 mergeSort(arr, 0, arr.length-1);
10 System.out.println(Arrays.toString(arr));
11 }
12
13 public static void mergeSort(int[] arr, int start, int end) {
14 int middle = (start + end) / 2;
15 if (start < end) {
16 //创造低位
17 mergeSort(arr, start, middle);
18 //创造高位
19 mergeSort(arr, middle + 1, end);
20 //调用归并
21 merge(arr, start, middle, end);
22 }
23 }
24
25 public static void merge(int[] arr, int start, int middle, int end) {
26 //用于存储归并后数据的临时数组
27 int[] temp = new int[end - start + 1];
28 //记录低位数组中遍历时的下标
29 int low = start;
30 //记录高位数组中遍历时的下标
31 int high = middle + 1;
32 //记录临时数组中数据下标
33 int index = 0;
34 //遍历两个数组取出小的数字，放入临时数组
35 while (low <= middle && high <= end) {
36 if (arr[low] <= arr[high]) {
37 temp[index] = arr[low];
38 low++;
39 } else {
40 temp[index] = arr[high];
41 high++;
42 }
43 index++;
44 }
45 //处理多余数据
46 while (low <= middle) {
47 temp[index++] = arr[low++];
48 }
49 while (high <= end) {
50 temp[index++] = arr[high++];
51 }
52 //将归并后的数据写入原数组
53 for (int i = 0; i ) {
54 arr[i + start] = temp[i];
55 }
56 }
57 }