原理:
代码和上图没关系:
package com.lyj.sort; public class MergeSort { /** * @param args */ public static void main(String[] args) { int[] array = { 1, 8, 6, 4, 10, 5, 3, 2, 22 }; mergeSort(array, 0, array.length - 1); } private static void mergeSort(int[] array, int start, int end) { if (start < end) { int mid = (start + end) / 2; mergeSort(array, start, mid); mergeSort(array, mid + 1, end); merge(array, start, mid, end); // 打印每次排序 for (int i : array) { System.out.print(i + " "); } System.out.println(); } } private static void merge(int[] array, int start, int mid, int end) { int[] temp = new int[end - start + 1]; int i = 0; int j = start; int k = mid + 1; // array的左子树和右子树都有元素 while (j <= mid && k <= end) { if (array[j] >= array[k]) { temp[i++] = array[k++]; } else { temp[i++] = array[j++]; } } // 将array的剩余元素装入temp while (j <= mid) temp[i++] = array[j++]; while (k <= end) temp[i++] = array[k++]; // 将temp的元素装入array for (int h = 0; h < temp.length; h++) { array[start + h] = temp[h]; } } }
排序过程: