import java.util.Arrays;/** * 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 * 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 * 归并排序是一种稳定的排序方法。 * <p> * 递归实现 */public class MergeSort { public static void main(String[] args) { // 测试次数 int times = 50000; int maxNum = 100; int maxSize = 100; for (int i = 0; i < times; i++) { // 生成随机数组 int[] arr1 = generateArray(maxNum, maxSize); // 复制 int[] arr2 = copyArray(arr1); // 归并排序 mergeSort(arr1); // Api排序 Arrays.sort(arr2); // 比较排序结果 if (!arrayEquals(arr1, arr2)) { System.out.println("Sort failed!!!"); System.out.println(Arrays.toString(arr1)); System.out.println(Arrays.toString(arr2)); return; } } System.out.println("Sort success"); } public static void mergeSort(int[] arr) { if (arr == null || arr.length < 2) { return; } sort(arr, 0, arr.length - 1); } public static void sort(int[] arr, int left, int right) { if (left == right) { return; } int mid = left + ((right - left) >> 1); sort(arr, left, mid); sort(arr, mid + 1, right); merge(arr, left, mid, right); } public static void merge(int[] arr, int left, int mid, int right) { int[] help = new int[right - left + 1]; int index = 0; int po1 = left; int po2 = mid + 1; while (po1 <= mid && po2 <= right) { help[index++] = arr[po1] < arr[po2] ? arr[po1++] : arr[po2++]; } while (po1 <= mid) { help[index++] = arr[po1++]; } while (po2 <= right) { help[index++] = arr[po2++]; } for (int i = left, j = 0; i <= right; ) { arr[i++] = help[j++]; } } /** * 生成随机数组 * * @param maxNum 最大数 * @param maxSize 数组最大大小 * @return 随机数组 */ private static int[] generateArray(int maxNum, int maxSize) { int[] arr = new int[(int) (maxSize * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) (maxNum * Math.random()) - (int) (maxNum * Math.random()); } return arr; } /** * 复制数组 * * @param arr 要复制的数组 * @return 复制的数组 */ private static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] copy = new int[arr.length]; for (int i = 0; i < arr.length; i++) { copy[i] = arr[i]; } return copy; } /** * 判断两数组是否完全相同 * * @param arr1 数组1 * @param arr2 数组2 * @return 是否相同 */ private static boolean arrayEquals(int[] arr1, int[] arr2) { if (arr1 == arr2) { return true; } if (arr1 == null || arr2 == null || arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; }}/* 如有错误，欢迎批评指正 */ 