排序算法之归并排序

思路：

利用递归的方式将数组不停的拆解，直到无法拆分为止。然后将其中的两个数组(拆解后的子数组)进行两两合并成一个有序数组，直到两个子数组合并后就是原数组则结束。

 具体两个数组如何合并成一个有序数组如下：

代码：

 1     /**
 2      * 归并排序
 3      * @param arr    需排序的数组
 4      * @param left   当前数组最左边的下标
 5      * @param right  当前数组最右边的下标
 6      * @param temp   临时数组
 7      */
 8     public static void mergeSort(int[] arr, int left, int right, int[] temp) {
 9         if (arr == null || arr.length == 0 || temp == null || temp.length == 0) {
10             return;
11         }
12         if (left >= right) {
13             return;
14         }
15 
16         //分：
17         //拆分数组的中轴
18         int pivot = (left + right) / 2;
19         //向左拆分
20         mergeSort(arr, left, pivot, temp);
21         //向右拆分
22         mergeSort(arr, pivot + 1, right, temp);
23 
24         //合：
25         //左边数组未排序中第一个元素的下标
26         int leftFirstIndex = left;
27         //左边数组最后一个元素的下标
28         int leftLastIndex = pivot;
29         //右边数组未排序中第一个元素的下标
30         int rightFirstIndex = pivot + 1;
31         //右边数组最后一个元素的下标
32         int rightLastIndex = right;
33         //临时数组未放入元素的第一个下标
34         int tempIndex = 0;
35         //将左边的有序数组和右边的有序数组按从小到大的顺序排入临时数组，直到某边数组的元素全部排完
36         while (leftFirstIndex <= leftLastIndex && rightFirstIndex <= rightLastIndex) {
37             if (arr[leftFirstIndex] <= arr[rightFirstIndex]) {
38                 //将较小的左边未排序的第一个元素追加到临时数组，leftFirstIndex后移一位
39                 temp[tempIndex] = arr[leftFirstIndex];
40                 leftFirstIndex++;
41             } else {
42                 //将较小的右边未排序的第一个元素追加到临时数组，rightFirstIndex后移一位
43                 temp[tempIndex] = arr[rightFirstIndex];
44                 rightFirstIndex++;
45             }
46             //tempIndex所指向的位置放了值，所以需后移一位
47             tempIndex++;
48         }
49         if (leftFirstIndex > leftLastIndex) {
50             //左边数组先排完，将右边数组剩下的值依次放入临时数组
51             while (rightFirstIndex <= rightLastIndex) {
52                 temp[tempIndex] = arr[rightFirstIndex];
53                 rightFirstIndex++;
54                 tempIndex++;
55             }
56         }
57         if (rightFirstIndex > rightLastIndex) {
58             //右边数组先排完，将左边数组剩下的值依次放入临时数组
59             while (leftFirstIndex <= leftLastIndex) {
60                 temp[tempIndex] = arr[leftFirstIndex];
61                 leftFirstIndex++;
62                 tempIndex++;
63             }
64         }
65         //临时数组未复制的第一个元素下标
66         int toCopyIndex = 0;
67         //将临时数组已排好序的元素复制到arr对应的位置[left, right]
68         while (left <= right) {
69             arr[left] = temp[toCopyIndex];
70             left++;
71             toCopyIndex++;
72         }
73     }