排序 - 归并排序 [2] 快来打我* 2021-12-05 04:31 186阅读 0赞 我们知道归并排序是拆分和合并两部分。 说完了归并排序的 [拆分部分][Link 1], 继续说说合并部分。 还是先回顾下拆分吧。 随便说个数组 \{ 9, 2, 7, 1, 3, 6, 5, 4\} 拆分过程: 9, 2, 7, 1 3, 6, 5,4 9, 2 7,1 3, 6 5, 4 9 2 7 1 3 6 5 4 好,到此我们对原数组完成了拆分,如果你不了解拆分,请一定看我的上一篇来弄懂拆分是如何工作的。 上面的拆分结果是最终的结果,其实合并是穿插在拆分过程中的。 当 9,2,7,1 --> 9,2 --> 9 & 2 的时候,9是某次递归中的左半部分,而2是这次递归中的右半部分。 当左半部分和右半部分都完成拆分的时候,我们就需要对他进行合并。 合并规则: 1. 创建一个数组,数组长度等于待合并左半部分和右半部分的数组元素总和; 2. 比较左面数组和右面数组中的第一个元素,选其较小者放入数组的第一个元素位置; 2.5. 如果左面数组和右面数组都只有一个元素,那么此时我们已经处理了其中一个,对上例来讲,我们已经把 右面数组的唯一元素:2 放入了数组中,那么就只剩下左面元素:9;再将9直接追加到新数组的后面即可; 3. 综合2和2.5,我们知道合并是这样进行的:总是选择两边较小的元素追加到新元素的下一个元素的位置; 4. 当其中一部分(左面部分或右面部分)处理完成后,将另一部分的所有元素直接追加到新数组的后面,如此完成合并。 合并过程如下: 9 2 7 1 3 6 5 4 2,9 1,7 3,6 4,5 1,2,7,9 3,4,5,6 1,2,3,4,5,6,7,9 我在上一篇中提到一个问题: 拆分的结果就是每个元素都被拆分为一个单元,那干脆直接将每个元素都当做一个单元来处理不就得了,干嘛还做什么拆分? 原因在合并过程中就体现出来了。 1. 细心点,你会发现每次合并的左右两半部分数组都是 有序 的,只有有序,才能用上面的合并的规则; 2. 拆分和合并是一个递归过程,递归,还是递归,还要花些时间理解。 这篇写的不好。心不在焉。。如果你看到觉得不明白,欢迎讨论。 package r; public class MyMergeSort { public static int[] array = {19, 1,90, 22, 11, 12, 9, 3}; public static void mergeSort(int[] sortArr, int start, int end) { int len = end - start; if (len < 1) return; else { int mid = start + len / 2; printArr(sortArr, start, mid); printArr(sortArr, mid + 1, end); System.out.println("======================"); mergeSort(sortArr, start, mid); mergeSort(sortArr, mid + 1, end); merge(sortArr, start, mid, mid+1, end); System.out.println("*************PRINT *********"); printArr(sortArr, start, end); } } private static void merge(int[] sortArr, int leftStart, int leftEnd, intrightStart, int rightEnd) { int leftPointer = leftStart; int rightPointer = rightStart; int[] sortedArr = new int[rightEnd -leftStart + 1]; int index = -1; while (leftPointer <= leftEnd &&rightPointer <= rightEnd) { index++; int s = getSmaller(sortArr, leftPointer,rightPointer); sortedArr[index] = sortArr[s]; if (s == leftPointer) leftPointer++; else rightPointer++; } if (leftPointer <= leftEnd) { for (int i = leftPointer; i <=leftEnd; i++) { sortedArr[++index] = sortArr[i]; } } if (rightPointer <= rightEnd) { for (int i = rightPointer; i <=rightEnd; i++) { sortedArr[++index] = sortArr[i]; } } // Copy back for (int i = 0; i < sortedArr.length;i++) { sortArr[leftStart + i] = sortedArr[i]; } } private static int getSmaller(int[] sortArr, int leftPointer, intrightPointer) { if (sortArr[leftPointer] <sortArr[rightPointer]) return leftPointer; else return rightPointer; } private static voidprintArr(int[] arr, int start, int end) { for (int i = start; i <= end; i++) { System.out.print(arr[i] + " "); } System.out.println("\r\n--------"); } public static void main(String[] args) { mergeSort(array, 0, array.length - 1); // printArr(array, 0, array.length - 1); } } [Link 1]: http://blog.csdn.net/chinalwb/article/details/9533813
还没有评论,来说两句吧...