19 -- 排序算法之归并排序

 从合并的示意图中可以看到，其实现思路与“合并两个有序的单链表，使之合并完后依然有序”类似。

 1 import java.util.Arrays;
 2 
 3 public class MergeSort {
 4 
 5     public static void main(String[] args) {
 6         int[] arr = {8,4,5,7,1,3,6,2};
 7         int[] tmp = new int[arr.length]; //中转数组
 8         mergeSort(arr, 0, arr.length - 1, tmp);
 9         System.out.println(Arrays.toString(arr));
10     }
11     
12     //分 + 合
13     public static void mergeSort(int[] arr,int left,int right,int[] tmp) {
14         if (left < right) {
15             int mid = (left + right) / 2;
16             //向左递归进行分解
17             mergeSort(arr, left, mid, tmp);
18             //向右递归进行分解
19             mergeSort(arr, mid+1, right, tmp);
20             System.out.println(left + "   " + right);
21             //合并
22             merge(arr, left, right,mid, tmp);
23         }
24     }
25 
26     //合并
27     /**
28      * 
29      * @param arr 待排序的数组
30      * @param left 左边有序数列的初始索引
31      * @param right 右边有序数列的初始索引
32      * @param mid 中间索引
33      * @param tmp 做中转的数组
34      */
35     public static void merge(int[] arr,int left,int right,int mid,int[] tmp) {
36         int i = left; //左边序列的第一个数的索引
37         int j = mid + 1; //右边序列的第一个数的索引
38         int t = 0; //放置tmp数组的索引位置
39         
40         //1、先把左右两边有序的数据按照规则填充到tmp数组，直到有一边的数据填充完毕
41         while(i <= mid && j <= right) {
42             if (arr[i] <= arr[j]) {  //左边有序序列当前元素小于或者等于左边有序序列的当前元素
43                 tmp[t] = arr[i]; //把左边当前元素填充到中转数组中
44                 i++; //左边有序序列继续向后遍历
45                 t++; //中转数组当前指向的位置后移，为下一个将要填充的数腾出位置
46             }else {
47                 tmp[t] = arr[j];
48                 j++;
49                 t++;
50             }
51         }
52         //2、把有剩余数据一边的数据依次填充到tmp数组中
53         while(i <= mid) { //说明左边有序序列还有剩余
54             tmp[t] = arr[i];
55             i++;
56             t++;
57         }
58         
59         while(j <= right) { //说明右边有序序列还有剩余
60             tmp[t] = arr[j];
61             j++;
62             t++;
63         }
64         //3、将tmp数组中的元素拷贝到arr数组中
65         //注：并非每次拷贝都是拷贝所有数据
66         t = 0;
67         int tmpLeft = left;
68         //第一次合并tmpLeft = 0 , right = 1 
69         //第二次合并tmpLeft = 2 , right = 3 
70         //第三次合并tmpLeft = 0 , right = 3
71         // ... ...
72         //最后一次(第七次)合并：tmpLeft = 0; right = 7
73         System.out.println("tmpLeft = " +  tmpLeft + "   right = " +  right);
74         while(tmpLeft <= right) {
75             arr[tmpLeft] = tmp[t];
76             tmpLeft++;
77             t++;
78         }
79     }
80     
81 }