【排序算法】02归并排序

归并排序运用分治思想来解决排序问题。

往ArraySorterUtils工具类中添加归并排序的实现，代码如下：

 1 package org.liws1.sort;
 2 
 3 import java.util.Arrays;
 4 import java.util.Comparator;
 5 
 6 /**
 7  * 数组的排序,这里统一做升序排序
 8  */
 9 public class ArraySorterUtils {
10 
11     public static class MergeSorter implements IArraySorter{
12         
13         @Override public <T extends Comparable<T>> void sort(T[] list) {
14             if(list != null && list.length > 1) {
15                 mergeLoop(list, 0, list.length - 1);
16             }
17         }
18 
19         @Override public <T> void sort(T[] list, Comparator<T> comp) {
20             // 实现省略，与sort(T[] list)没差
21         }
22         
23         /**
24          * 归并排序的递归逻辑部分：
25          *    使srcDatas的"[start~end]片段"有序
26          * @param srcDatas
27          * @param start
28          * @param end
29          */
30         private static <T extends Comparable<T>> void mergeLoop(T[] srcDatas, int start, int end) {
31             if(start != end){
32                 int middle = (start + end) / 2;
33                 mergeLoop(srcDatas, start, middle);
34                 mergeLoop(srcDatas, middle + 1, end);
35                 merge(srcDatas, start, middle, end);
36             }
37         }
38 
39         /**
40          * 归并排序的基本操作: 
41          *    将两个位置相邻的 有序记录子序列 srcDatas[start~middle] 和 srcDatas[middle+1~end]
42          * 归并为一个有序记录序列 srcDatas[start~end] 。
43          * @param srcDatas
44          * @param start
45          * @param middle
46          * @param end
47          */
48         private static <T extends Comparable<T>> void merge(T[] srcDatas, int start, int middle, int end) {
49             // 创建1个临时数组，用于临时存放归并后的有序记录序列
50             @SuppressWarnings("unchecked")
51             T[] tempArr = (T[]) new Comparable[srcDatas.length];    
52             
53             // 1、归并两个子序列 srcDatas[start~middle] 和  srcDatas[middle+1~end] 到 destDatas[start~end]
54             int p = start;         // p遍历srcDatas[start~middle]
55             int q = middle + 1; // q遍历srcDatas[middle+1~end]
56             int r = start;         // r指向destDatas[start~end]
57             for (; p <= middle && q <= end; r++) {
58                 if (srcDatas[p].compareTo(srcDatas[q]) <= 0) {
59                     tempArr[r] = srcDatas[p++];
60                 } else {
61                     tempArr[r] = srcDatas[q++];
62                 }
63             }
64             // 将两个有序记录子序列中剩下的记录也复制到destDatas【下面两个while循环只可能走其中一个】
65             while(p <= middle){
66                 tempArr[r++] = srcDatas[p++];
67             }
68             while(q <= end){
69                 tempArr[r++] = srcDatas[q++];
70             }
71             
72             // 2、将临时数组中[start~end]的内容拷贝回原数组相应位置中  
73             for (int i = start; i <= end; i++) {
74                 srcDatas[i] = tempArr[i];
75             }
76         }
77 
78     }
79 
80 }

测试代码如下：

 1 package org.liws1.sort;
 2 
 3 import java.util.Arrays;
 4 import org.junit.Test;
 5 
 6 public class _Test {
 7 
 8     private Integer[] datas = { 30, 1, 29, 2, 28, 3, 27, 4, 26, 5, 25, 6, 24, 7,
 9             23, 8, 22, 9, 21, 10, 20, 19, 15, 18, 12, 17, 11, 16, 14, 13 };
10     
11     @Test public void testMerge(){
12         new ArraySorterUtils.MergeSorter().sort(datas);
13         System.out.println(Arrays.toString(datas));
14     } // out:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
15 }