package sort; /** * Created by ozc on 2018/3/19. * * @author ozc * @version 1.0 */ public class MergeSort { public static void main(String[] args) { /*int[] arrays = {9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8}; sort.MergeSort(arrays, 0, arrays.length - 1); System.out.println("公众号：Java3y" + arrays);*/ System.out.println("Hello World"); } /** * 归并排序 * * @param arrays * @param L 指向数组第一个元素 * @param R 指向数组最后一个元素 */ public static void mergeSort(int[] arrays, int L, int R) { //如果只有一个元素，那就不用排序了 if (L == R) { return; } else { //取中间的数，进行拆分 int M = (L + R) / 2; //左边的数不断进行拆分 mergeSort(arrays, L, M); //右边的数不断进行拆分 mergeSort(arrays, M + 1, R); //合并 merge(arrays, L, M + 1, R); } } /** * 合并数组 * * @param arrays * @param L 指向数组第一个元素 * @param M 指向数组分隔的元素 * @param R 指向数组最后的元素 */ public static void merge(int[] arrays, int L, int M, int R) { //左边的数组的大小 int[] leftArray = new int[M - L]; //右边的数组大小 int[] rightArray = new int[R - M + 1]; //往这两个数组填充数据 for (int i = L; i < M; i++) { leftArray[i - L] = arrays[i]; } for (int i = M; i <= R; i++) { rightArray[i - M] = arrays[i]; } int i = 0, j = 0; // arrays数组的第一个元素 int k = L; //比较这两个数组的值，哪个小，就往数组上放 while (i < leftArray.length && j < rightArray.length) { //谁比较小，谁将元素放入大数组中,移动指针，继续比较下一个 if (leftArray[i] < rightArray[j]) { arrays[k] = leftArray[i]; i++; k++; } else { arrays[k] = rightArray[j]; j++; k++; } } //如果左边的数组还没比较完，右边的数都已经完了，那么将左边的数抄到大数组中(剩下的都是大数字) while (i < leftArray.length) { arrays[k] = leftArray[i]; i++; k++; } //如果右边的数组还没比较完，左边的数都已经完了，那么将右边的数抄到大数组中(剩下的都是大数字) while (j < rightArray.length) { arrays[k] = rightArray[j]; k++; j++; } } }