~~~ package Sort; /** * 二分归并排序，平均划分数组，递归划分，合并 * * @author lucky-django * */ public class MergeSort { /** * 合并操作 */ public void merge(int[] array, int startIndex, int midIndex, int endIndex) { int x = midIndex - startIndex;// 前一个数组的最大index int y = endIndex - midIndex - 1;// 后一个数组的最大index int[] firstArray = new int[midIndex - startIndex + 1]; int[] secondArray = new int[endIndex - midIndex]; // 将原数组复制到两个子数组中 for (int i = 0; i <= x; i++) { firstArray[i] = array[i + startIndex]; } for (int i = 0; i <= y; i++) { secondArray[i] = array[i + midIndex + 1]; } int i = 0, j = 0, k = startIndex; while (i <= x && j <= y) { if (firstArray[i] <= secondArray[j]) { array[k] = firstArray[i]; i++; } else { array[k] = secondArray[j]; j++; } k++; } if (i > x) { for (; j <= y; j++) { array[k] = secondArray[j]; k++; } } else { for (; i <= x; i++) { array[k] = firstArray[i]; k++; } } } /** * 划分+合并 */ public void mergeSort(int[] array, int startIndex, int endIndex) { if (startIndex >= endIndex) { return; } int mid = (startIndex + endIndex) / 2; mergeSort(array, startIndex, mid); mergeSort(array, mid + 1, endIndex); merge(array, startIndex, mid, endIndex); } public static void main(String[] args) { int[] array = new int[] { 8, 2, 4, 6 }; MergeSort sort = new MergeSort(); sort.mergeSort(array, 0, 3); for (int i = 0; i < array.length; i++) { System.out.println(array[i]); } } } ~~~