归并排序(非递归)：自底向上
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); int i = left; int j = mid + 1; for (int t = left; t <= right; t++) { if (i > mid) { arr[t] = aux[j++ - left]; } else if (j > right) { arr[t] = aux[i++ - left]; } else if (aux[i - left].compareTo(aux[j - left]) < 0) { arr[t] = aux[i++ - left]; } else { arr[t] = aux[j++ - left]; } } } public static > void sort(T[] arr, int left, int right) { int n = arr.length; for (int size = 1; size < n; size *= 2) { for (int i = 0; i < n - size; i += size * 2) { merge(arr, i, i + size - 1, Math.min(i + 2 * size - 1, n - 1)); } } } 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 }} 归并排序(非递归)优化：merge前判断是否有必要进行归并
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); int i = left; int j = mid + 1; for (int t = left; t <= right; t++) { if (i > mid) { arr[t] = aux[j++ - left]; } else if (j > right) { arr[t] = aux[i++ - left]; } else if (aux[i - left].compareTo(aux[j - left]) < 0) { arr[t] = aux[i++ - left]; } else { arr[t] = aux[j++ - left]; } } } public static > void sort(T[] arr, int left, int right) { int n = arr.length; for (int size = 1; size < n; size *= 2) { for (int i = 0; i < n - size; i += size * 2) { if (arr[i + size - 1].compareTo(arr[i + size]) > 0) { merge(arr, i, i + size - 1, Math.min(i + 2 * size - 1, n - 1)); } } } } 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 }} 递归排序(非递归)继续优化：对小规模数据使用插入排序
归并排序是对一组一组的数据进行归并。当这一组中的数很少时(暂定为4)，使用插入排序。
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); int i = left; int j = mid + 1; for (int t = left; t <= right; t++) { if (i > mid) { arr[t] = aux[j++ - left]; } else if (j > right) { arr[t] = aux[i++ - left]; } else if (aux[i - left].compareTo(aux[j - left]) < 0) { arr[t] = aux[i++ - left]; } else { arr[t] = aux[j++ - left]; } } } 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]; j--; } arr[j + 1] = temp; } } public static > void sort(T[] arr, int left, int right) { int len = arr.length; int smallSize = 4;//当规模小于4时采用插入排序 for (int i = 0; i < len; i += smallSize) { insertionSort(arr, i, Math.min(i + smallSize - 1, len - 1)); } for (int size = smallSize; size < len; size *= 2) { for (int i = 0; i < len - size; i += size * 2) { if (arr[i + size - 1].compareTo(arr[i + size]) > 0){ merge(arr, i, i + size - 1, Math.min(i + 2 * size - 1, len - 1)); } } } } 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 }}