【搞定算法】归并排序及其解决逆序对数、小和问题

电玩女神 2021-12-14 03:49 187阅读 0赞

归并排序也是分治法一个很好的应用，**先递归到最底层，然后从下往上每次两个序列进行归并合起来，是一个由上往下分开，再由下往上合并的过程**。

而对于每一次合并操作，对于每一次 merge 的操作过程如下：

1、准备一个额外的数组（help），使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

2、设定两个指针，最初位置分别为两个已经排序序列的起始位置；

3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

4、重复步骤3直到某一指针达到序列尾；

5、将另一序列剩下的所有元素直接复制到合并序列尾；

看下面的例子合并过程如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

## 1、归并排序的代码实现 ##

public class MergeSort {
    
        public static void mergeProcess(int[] arr){
            if(arr == null || arr.length < 1){
                return;
            }
            mergeProcess(arr, 0, arr.length - 1);
        }
    
        public static void mergeProcess(int[] arr, int left, int right){
            if(left > right){
                return;
            }
            int mid = left + ((right -left) >> 1);
            mergeProcess(arr, left, mid);
            mergeProcess(arr, mid + 1, right);
            if(arr[mid] > arr[mid + 1]){
                merge(arr, left, mid, right);
            }
        }
    
        public static void merge(int[] arr, int left, int mid, int right){
            int[] help = new int[right - left + 1];
            int k = 0;
            int p1 = left, p2 = mid + 1;
            while(p1 <= mid && p2 <= right){
                // 左右两边相等，就先拷贝左边的（可以保证稳定性）
                help[k++] = arr[p1] <= arr[p2] ? arr[p1] : arr[p2];
            }
            while(p1 <= mid){
                help[k++] = arr[p1++];
            }
            while(p2 <= right){
                help[k++] = arr[p2++];
            }
            // 拷贝回原数组
            for(int i = 0; i < k; i++){
                arr[i + left] = help[i];
            }
        }
    }

注意几点:

1、mergeProcess(arr, L, mid)，不是mid-1；

2、注意上面的代码中if(arr\[mid\] > arr\[mid+1\])防止一开始数组很有序的情况；

3、注意在外排比较的时候，为了保证稳定性，左右相等的时候，先拷贝左边的。

## 2、逆序对数问题 ##

另外再补充一个[LintCode532Reverse Pairs归并排序求解逆序数][LintCode532Reverse Pairs]的问题:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1][]

这个的关键在于，**在合并** **l ~ mid** **和** **mid+1~r** **的过程中，只要** **arr\[p1\] > arr\[p2\]****，则** **arr\[p2\]** **和** **arr\[p1 ~ mid\]** **都能组成逆序对，所以我们每次都可以加上** **mid - p1 + 1** **个数，故可以方便求出逆序数对数**。

public class ReversePairsByMergeSort {
    
        public static long reversePairs(int[] arr){
            if(arr == null || arr.length <= 1){
                return 0;
            }
            return mergeProcess(arr, 0, arr.length - 1);
        }
    
        public static long mergeProcess(int[] arr, int left, int right){
            if(left == right){
                return  0;
            }
            int mid = left + ((right - left) >> 1);
            return mergeProcess(arr, left, mid)
                    + mergeProcess(arr, mid + 1, right)
                    + merge(arr, left, mid, right);
        }
    
        public static long merge(int[] arr, int left, int mid, int right){
            int[] help = new int[right - left + 1];
            int k = 0;
            long sum = 0; // 逆序对数
            int p1 = left;
            int p2 = mid + 1;
            while(p1 <= mid && p2 <= right){
                if(arr[p1] <= arr[p2]){
                    help[k++] = arr[p1++];
                }else{
                    // arr[p1] > arr[p2] 此时p2都小于arr[p1,mid]之间的元素
                    sum += mid - p1 + 1;
                    help[k++] = arr[p2++];
                }
            }
            while(p1 <= mid){
                help[k++] = arr[p1++];
            }
            while(p2 <= right){
                help[k++] = arr[p2++];
            }
            for(int i = 0; i < k; i++){
                arr[i + left] = help[i];
            }
            return sum;
        }
    
        public static void main(String[] args) {
            int[] arr = {3,2,1};
            System.out.println(reversePairs(arr));
        }
    }

## 3、小和问题 ##

还有一个题目就是小和问题: 具体的问题和上面的逆序数差不多。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 2][]

public class MinSumByMergeSort {
    
        public static int getMinSum(int[] arr){
            if(arr == null || arr.length <= 1){
                return 0;
            }
            return mergeProcess(arr, 0, arr.length - 1);
        }
    
        public static int mergeProcess(int[] arr, int left, int right){
            if(left == right){
                return 0;
            }
            int mid = left + ((right - left) >> 1);
            return mergeProcess(arr, left, mid)
                    + mergeProcess(arr, mid + 1, right)
                    + merge(arr, left, mid, right);
        }
    
        public static int merge(int[] arr, int left, int mid, int right){
            int[] help = new int[right - left + 1];
            int k = 0, sum = 0;
            int p1 = left, p2 = mid + 1;
            while(p1 <= mid && p2 <= right){
                if(arr[p1] < arr[p2]){
                    //  如果arr[p1] < arr[p2] 则arr[p1] < arr[p2 ~ R]
                    sum += arr[p1] * (right - p2 + 1);
                    help[k++] = arr[p1++];
                }else{
                    help[k++] = arr[p2++];
                }
            }
            while(p1 <= mid){
                help[k++] = arr[p1++];
            }
            while(p2 <= right){
                help[k++] = arr[p2++];
            }
            for(int i = 0; i <= k; i++){
                arr[i + left] = help[i];
            }
            return sum;
        }
    }

## 4、补充 ##

另外，归并排序也可以自底向上的进行：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 3][]

代码实现注意两个细节:

1、第二层循环: sz + i -1 = mid ，注意不要越界，所以在第二层循环中 i+sz < arr.length；

2、同理，i+2\*sz - 1也要保证不能越界，所以和arr.length - 1取最小值。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20211213/17bb8f0c88b84bd29fc22f817859ce73.png
[LintCode532Reverse Pairs]: https://www.lintcode.com/problem/reverse-pairs/description
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1]: /images/20211213/71929b4b670b49aaba4072f348dc1ea0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 2]: /images/20211213/9fc7c8cb6e804cd58bb91de9ffb485e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 3]: /images/20211213/78433d17c5b04260b2b3f949a5b1434d.png