排序 - 归并排序 [2]

快来打我* 2021-12-05 04:31 225阅读 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