1. package sort;
    4. /**
    5.  * 归并排序相比较之前的排序算法而言加入了分治法的思想，其算法思路如下：
    6.  *
    7.  * 1.如果给的数组只有一个元素的话，直接返回（也就是递归到最底层的一个情况）
    8.  *
    9.  * 2.把整个数组分为尽可能相等的两个部分（分）
    10.  *
    11.  * 3.对于两个被分开的两个部分进行整个归并排序（治）
    12.  *
    13.  * 4.把两个被分开且排好序的数组拼接在一起
    14.  */
    15. public class Merge<T extends Comparable<T>> {
    17.     public void mergeArr(T[] arr, int l, int mid, int r){
    19.         T[] aux = (T[])(new Object[r - l + 1]);
    21.         for(int i = l; i <= r; i++)
    22.             aux[i - l] = arr[i];
    24.         //双指针操作
    25.         int i = l, j = mid + 1;
    26.         for(int k = l; k <= r; k++){
    28.             if(i > mid){
    29.                 arr[k] = aux[j - l];
    30.                 j++;
    31.             }else if(j > r){
    32.                 arr[k] = aux[i - l];
    33.                 i++;
    34.             }else if(aux[i-l].compareTo(aux[j - l]) < 0){
    35.                 arr[k] = aux[i - l];
    36.                 i ++;
    37.             }else{
    38.                 arr[k] = aux[j - l];
    39.                 j ++;
    40.             }
    41.         }
    42.     }
    44.     //递归使用递归排序， 对arr[l...r]的范围进行排序
    45.     public void merge(T[] arr, int l, int r){
    47. //        if( l >= r)
    48. //            return;
    49.         if(r - l <= 15){
    50.             insertionSort(arr, l, r);
    51.             return;
    52.         }
    54.         int mid = (l + r) / 2;
    55.         merge(arr, l, mid);
    56.         merge(arr, mid + 1, r);
    57.         if(arr[mid].compareTo(arr[mid + 1]) > 0)
    58.             mergeArr(arr, l, mid, r);
    59.     }
    61.     private void insertionSort(T[] arr, int l, int r) {
    63.         for(int i = l + 1; i <= r; i++){
    65.             T t = arr[i];
    66.             int j;
    67.             //依次循环将数据后移一个位置， 最后在插入
    68.             for(j = i; j > l && arr[j - 1].compareTo(t) > 0; j--)
    69.                 arr[j] = arr[j - 1];
    71.             arr[j - 1] = t;
    72.         }
    73.         return;
    74.     }
    76.     public void mergeSort(T[] arr, int n){
    78.         merge(arr, 0, n - 1);
    79.     }
    81.     /**
    82.      * 以下是经典的归并排序算法
    83.      * @param arr  数组
    84.      * @param l    左边界
    85.      * @param r    右边界
    86.      */
    87.     void mergeSort(int[] arr, int l, int r) {
    88.         if (l < r) {
    89.             int m = l+(r-l)/2;
    91.             mergeSort(arr, l, m);
    92.             mergeSort(arr, m+1, r);
    94.             merge(arr, l, m, r);
    95.         }
    96.     }
    98.     private void merge(int[] arr, int l, int m, int r) {
    99.         int i, j, k;
    100.         int n1 = m - l + 1;
    101.         int n2 =  r - m;
    103.         int[] L = new int[n1];
    104.         int[] R = new int[n2];
    106.         /*
    107.         拷贝新数组
    108.          */
    109.         for (i = 0; i < n1; i++)
    110.             L[i] = arr[l + i];
    111.         for (j = 0; j < n2; j++)
    112.             R[j] = arr[m + 1+ j];
    114.         i = 0;
    115.         j = 0;
    116.         k = l;
    117.         /*
    118.          * 对两个数组在不越界的情况下，分别拷贝数组直到一个数组越界
    119.          */
    120.         while (i < n1 && j < n2) {
    121.             if (L[i] <= R[j]) {
    122.                 arr[k] = L[i];
    123.                 i++;
    124.             }else {
    125.                 arr[k] = R[j];
    126.                 j++;
    127.             }
    128.             k++;
    129.         }
    131.         /*
    132.         将不越界的数组拷贝到新数组中
    133.          */
    134.         while (i < n1) {
    135.             arr[k] = L[i];
    136.             i++;
    137.             k++;
    138.         }
    140.         while (j < n2) {
    141.             arr[k] = R[j];
    142.             j++;
    143.             k++;
    144.         }
    145.     }
    147. }