排序算法在数组题目中的应用

太过爱你忘了你带给我的痛 2022-04-11 13:38 184阅读 0赞

在做题目中可能会发现一些类型的题目具有一定的解题倾向性。在数组题目中，跟数组中大小顺序有关，往往可以使用排序算法，并在排序的过程中，做相应的处理。这种思路在二叉树题目尤其突出，二叉树的题目很多情况下都是需要遍历二叉树。根据题目还需要选择相应的排序算法或者二叉树遍历类型。

在剑指offer中有一道关于数组中逆序对的题目，这道题就很好的体现了排序算法在数组中的应用。

--------------------

题目描述  
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

[数组中的逆序对，题目详细链接][Link 1]

--------------------

这道题的核心思想就是使用归并排序的思想，并在合并子数组的时候，对数组中的逆序对进行统计，代码如下。

public class Solution {
        public static int InversePairs(int [] array) {
            if(array == null || array.length == 0)
                return 0;
    
            //辅助数组
            int[] copy = new int[array.length];
            for(int i=0; i<array.length; i++){
                copy[i] = array[i];
            }
    
            int count = InversePairsCore(array, copy, 0, array.length-1);
            return count;
        }
    
        private static int InversePairsCore(int[] array, int[] copy, int low, int high){
            if(low == high)
                return 0;
    
            //将数组分成两部分,左边的low到mid,和右边的mid+1到high,递归计算左边和右边总共有多少对逆序对
            int mid = (low+high)/2;
            //递归调用
            int leftCount = InversePairsCore(array, copy, low, mid)%1000000007;
            int rightCount = InversePairsCore(array,copy, mid+1, high)%1000000007;
            //以上部分就是归并排序中的拆分部分, 下面是归并部分
    
            int count = 0;
            //i初始化为前半段最后一个数组的下标, 指向前半部分的数组的最后一个元素
            int i = mid;
            //j初始化为后半段最后一个数字的下标, 指向后半部分的数组的最后一个元素
            int j = high;
            int locCopy = high;
            //这里是循环合并相邻的子数组,是循环比较左右边中的数组的每个元素
            //这里的数组都是排好序的,如果array[i]大于此时的array[j],则array[i]大于mid+1到j的所有元素
            //这样此时的i就与mid+1到j的元素都组成一对逆序对
    
            //合并并且计算这两个相邻数组的逆序对的个数, 归并排序的归并部分
            while(i >= low && j >= mid + 1){
                //这里都是从左右数组的最后一位开始的,然后一位一位向后循环的
                if(array[i] > array[j]){
                    //如果array[i]大于array[j], 则array[i]大于从array[mid+1]到array[j]的所有元素, 即增加了逆序对 j-mid 个
                    count = count + j - mid;
                    //这里是合并后的数组,此时将array[i]放到最终合并数组空着的最后一位
                    copy[locCopy--] = array[i--];
                    if(count >= 1000000007)
                        count %= 1000000007;
                }else{
                    //其实这里合并后的数组,就是将array[i]和array[j]中较大者,
                    //依次放到合并数组空着的最后一位
                    copy[locCopy--] = array[j--];
                    //copy[locCopy] = array[j];
                    //locCopy--;
                    //j--;
                }
            }
    
            //如果当前半部分或者后半部分中有一个数组已经在上边的while循环遍历完了, 但是另一个数组还没有遍历完
            //因为这两个数组都是自身已经排序好了, 所以只需要将剩余的元素依次放到辅助数组中即可
            //以下两个循环最多只可能执行一个
            for(;i>=low;i--){
                copy[locCopy--] = array[i];
            }
    
            for(;j>=mid+1; j--){
                copy[locCopy--] = array[j];
            }
    
            //这里是复用了原数组的变量, 将已经排序好的数组部分, 复制回原数组部分
            for(int s = low; s <= high; s++){
                array[s] = copy[s];
            }
    
            return (leftCount + rightCount + count)%1000000007;
        }
    
        public static void main(String[] args) {
            int[] array = {7,5,6,4};
            int result = InversePairs(array);
            System.out.println(result);
        }
    }

运行结果

[Link 1]: https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=13&tqId=11188&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking