普通归并排序

public class MergeSort {    /**     * @param arr   待排序的数组     * @param left  本次归并的左边界     * @param mid   本次归并的中间位置，也就是分界线     * @param right 本次归并的右边界     * @param 
     
         泛型     * @local aux   辅助空间(Auxiliary Space)     */    private static 
      
       > void merge(T[] arr, int left, int mid, int right) {        T[] aux = java.util.Arrays.copyOfRange(arr, left, right + 1);        //aux，i j分别是这两半的起始指针。将这两个闭区间归并[left ... mid]   [mid + 1 ... right]        int i = left;        int j = mid + 1;        for (int t = left; t <= right; t++) {//把arr数组中的[left...right]区间都覆盖了，就完事了            if (i > mid) { //i == mid + 1 时越界(跃出左半数组)                arr[t] = aux[j++ - left];            } else if (j > right) {//j == right + 1 时越界(跃出右半数组)                arr[t] = aux[i++ - left];            } else if (aux[i - left].compareTo(aux[j - left]) < 0) {//如果i-left小，那么插入。(左半边数组的指针所指的数小)                arr[t] = aux[i++ - left];            } else { //如果j-left小，那么插入。(右半边数组的指针所指的数小)                arr[t] = aux[j++ - left];            }        }    }    private static 
       
        > void sort(T[] arr, int left, int right) {        if (left >= right) {            return;        }        int mid = (left + right) / 2;        sort(arr, left, mid);        sort(arr, mid + 1, right);        merge(arr, left, mid, right);    }    public static 
        
         > void sort(T[] arr) {        sort(arr, 0, arr.length - 1);    }    private static void printArr(Object[] arr) {        for (Object o : arr) {            System.out.print(o);            System.out.print("\t");        }        System.out.println();    }    public static void main(String args[]) {        Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};        printArr(arr);//3   5   1   7   2   9   8   0   4   6        sort(arr);        printArr(arr);//0   1   2   3   4   5   6   7   8   9    }}
        
       
      
     

归并优化：利用插入排序

当递归到规模足够小时，利用插入排序 

public class MergeSort {    /**     * @param arr   待排序的数组     * @param left  本次归并的左边界     * @param mid   本次归并的中间位置，也就是分界线     * @param right 本次归并的右边界     * @param 
     
         泛型     * @local aux   辅助空间(Auxiliary Space)     */    private static 
      
       > void merge(T[] arr, int left, int mid, int right) {        T[] aux = java.util.Arrays.copyOfRange(arr, left, right + 1);        //aux，i j分别是这两半的起始指针。将这两个闭区间归并[left ... mid]   [mid + 1 ... right]        int i = left;        int j = mid + 1;        for (int t = left; t <= right; t++) {//把arr数组中的[left...right]区间都覆盖了，就完事了            if (i > mid) { //i == mid + 1 时越界(跃出左半数组)                arr[t] = aux[j++ - left];            } else if (j > right) {//j == right + 1 时越界(跃出右半数组)                arr[t] = aux[i++ - left];            } else if (aux[i - left].compareTo(aux[j - left]) < 0) {//如果i-left小，那么插入。(左半边数组的指针所指的数小)                arr[t] = aux[i++ - left];            } else { //如果j-left小，那么插入。(右半边数组的指针所指的数小)                arr[t] = aux[j++ - left];            }        }    }    /**     * @param arr   当规模小的时候对arr采用插入排序     * @param left  待排序部分的左边界     * @param right 待排序部分的右边界     * @param 
       
           泛型     */    private static 
        
         > void insertionSort(T[] arr, int left, int right) {        for (int i = left + 1; i <= right; i++) {            T temp = arr[i];            int j = i - 1;            while (j >= 0 && temp.compareTo(arr[j]) < 0) {                arr[j + 1] = arr[j];                j--;            }            arr[j + 1] = temp;        }    }    private static 
         
          > void sort(T[] arr, int left, int right) {        if (right - left < 7) { //对小规模数据进行插入排序            insertionSort(arr, left, right);            return;        }        int mid = (left + right) / 2;        sort(arr, left, mid);        sort(arr, mid + 1, right);        merge(arr, left, mid, right);    }    public static 
          
           > void sort(T[] arr) { sort(arr, 0, arr.length - 1); } private static void printArr(Object[] arr) { for (Object o : arr) { System.out.print(o); System.out.print("\t"); } System.out.println(); } public static void main(String args[]) { Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; printArr(arr);//3 5 1 7 2 9 8 0 4 6 sort(arr); printArr(arr);//0 1 2 3 4 5 6 7 8 9 }}　　
          
         
        
       
      
     

归并排序继续优化：归并前判断一下是否还有必要归并

public class MergeSort {    /**     * @param arr   待排序的数组     * @param left  本次归并的左边界     * @param mid   本次归并的中间位置，也就是分界线     * @param right 本次归并的右边界     * @param 
     
         泛型     * @local aux   辅助空间(Auxiliary Space)     */    private static 
      
       > void merge(T[] arr, int left, int mid, int right) {        T[] aux = java.util.Arrays.copyOfRange(arr, left, right + 1);        //aux，i j分别是这两半的起始指针。将这两个闭区间归并[left ... mid]   [mid + 1 ... right]        int i = left;        int j = mid + 1;        for (int t = left; t <= right; t++) {//把arr数组中的[left...right]区间都覆盖了，就完事了            if (i > mid) { //i == mid + 1 时越界(跃出左半数组)                arr[t] = aux[j++ - left];            } else if (j > right) {//j == right + 1 时越界(跃出右半数组)                arr[t] = aux[i++ - left];            } else if (aux[i - left].compareTo(aux[j - left]) < 0) {//如果i-left小，那么插入。(左半边数组的指针所指的数小)                arr[t] = aux[i++ - left];            } else { //如果j-left小，那么插入。(右半边数组的指针所指的数小)                arr[t] = aux[j++ - left];            }        }    }    /**     * @param arr   当规模小的时候对arr采用插入排序     * @param left  待排序部分的左边界     * @param right 待排序部分的右边界     * @param 
       
           泛型     */    private static 
        
         > void insertionSort(T[] arr, int left, int right) {        for (int i = left + 1; i <= right; i++) {            T temp = arr[i];            int j = i - 1;            while (j >= 0 && temp.compareTo(arr[j]) < 0) {                arr[j + 1] = arr[j];                j--;            }            arr[j + 1] = temp;        }    }    private static 
         
          > void sort(T[] arr, int left, int right) {//        先注释掉，为了测试//        if (right - left < 7) { //对小规模数据进行插入排序//            insertionSort(arr, left, right);//            return;//        }        if (left >= right) {            return;        }        int mid = (left + right) / 2;        sort(arr, left, mid);        sort(arr, mid + 1, right);        //在归并前判断一下，如果左边的最大的比右边的最小的还小(或者等于)，那就不用归并了，已经有序了。        if (arr[mid].compareTo(arr[mid + 1]) <= 0) {            return;        }        merge(arr, left, mid, right);    }    public static 
          
           > void sort(T[] arr) { sort(arr, 0, arr.length - 1); } private static void printArr(Object[] arr) { for (Object o : arr) { System.out.print(o); System.out.print("\t"); } System.out.println(); } public static void main(String args[]) { Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; printArr(arr);//3 5 1 7 2 9 8 0 4 6 sort(arr); printArr(arr);//0 1 2 3 4 5 6 7 8 9 }}　　
          
         
        
       
      
     

归并排序继续优化：只在排序前开辟一次空间

public class MergeSort {    public static 
     
      > void sort(T[] arr) {        T[] aux = (T[]) new Comparable[arr.length];        sort(arr, aux, 0, arr.length - 1);    }    private static 
      
       > void sort(T[] arr, T[] aux, int left, int right) {        if (right - left < 4) {            insertionSort(arr, left, right);            return;        }//        if (left >= right) {//            return;//        }        int mid = (left + right) / 2;        sort(arr, aux, left, mid);        sort(arr, aux, mid + 1, right);        if (arr[mid].compareTo(arr[mid + 1]) > 0) {            merge(arr, aux, left, mid, right);        }    }    private static 
       
        > void merge(T[] arr, T[] aux, int left, int mid, int right) {        System.arraycopy(arr, left, aux, left, right - left + 1);        int i = left;        int j = mid + 1;        for (int t = left; t <= right; t++) {            if (i > mid) {                arr[t] = aux[j++];            } else if (j > right) {                arr[t] = aux[i++];            } else if (aux[i].compareTo(aux[j]) < 0) {                arr[t] = aux[i++];            } else {                arr[t] = aux[j++];            }        }    }    private static 
        
         > void insertionSort(T[] arr, int left, int right) {        for (int i = left + 1; i <= right; i++) {            T temp = arr[i];            int j = i - 1;            while (j >= left && temp.compareTo(arr[j]) < 0) {                arr[j + 1] = arr[j--];            }            arr[j + 1] = temp;        }    }    private static void printArr(Object[] arr) {        for (Object o : arr) {            System.out.print(o);            System.out.print("\t");        }        System.out.println();    }    public static void main(String args[]) {        Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};        printArr(arr);//3   5   1   7   2   9   8   0   4   6        sort(arr);        printArr(arr);//0   1   2   3   4   5   6   7   8   9    }}