Chapter3: 更好的查找与排序算法

9. 用归并排序思想解两道关于逆序对的题目

合并有序数组

题目

给定两个排序后的数组A和B，其中A的末端有足够的缓冲空间容纳B。编写一个方法，将B合并入A并排序

算法

基本思想

其实就是归并排序，只不过不是用额外的空间，空间已经给你了

• 设置一个指针pc 指数组A的第 arrALen+arrBlen 个元素，即A[arrALen+arrBLen-1] (即合并数组A和B后的最后一个元素)
• 就是让一个指针 pa 初始化为数组A最后一个有值的元素的位置，一个指针 pb 初始化为数组B最后一个元素
• 比较pa 和在 pb 的值，选取较大的值放到 pc 的位置上，指向较大值的指针向前移动1位，pc 指针向前移动1位，循环直到遍历完数组A或B，如果遍历完AB还有剩下的就直接复制过去

遍历数组B，一个指针遍历数组A,选择大的数往后放

逆序对个数

题目

一个数列，如果左边的数大，右边的数小，则称这两个数为一个逆序对(这两个数的位置不一定连续)。求出一个数列中有多少个逆序对。

比如数列{4,3,5,2},有{4,3},{4,2},{3,2},{5,2}四对逆序对。

算法

解法1：暴力解法

用两层for循环判断分别每个元素 i 与其之后的每个元素的大小关系，时间复杂度为O(n^2);

解法2：用归并排序的思想

基本思想

• 首先要明白归并排序在归并的递归调用中，会以中间坐标的元素为边界，将数组分为左右两部分，其中左边和右边部分它们分别是有序递增的(但是整个数组并不一定有序，比如 [2,4,6,8,1,3,4,6]，左边的元素也不一定比右边小

• 假设归并排序过程中某层递归的划分为：数组为 左：{2，4，6，8} 右：{1，3，4，6}

  归并排序和合并的时候(看下面的 merge 函数),思想是遍历比较左右两个数组，选取小的元素到辅助数组里 ，假设左右数组当前正在比较中的元素为 left 和 right ,观察发现，因为左右两个数组都是分别递增的，所以当较小元素为 right时 ，那么左数组中 [left,mid]( mid 为左数组最后一个元素的下标) 共 mid-left+1个元素都是比 right 大的，即有 mid-left+1 个逆序对，当遍历完左数组或右数组，就知道全部的逆序对个数。(因为两边分别递增，所以逆序对的两个元素只可能分别分布在左右数组中)

• 可能会有疑问的是，在划分合并过程中元素的位置被改变了，那统计的结果还是正确的么?归并实际的过程是：

  在层层的递归调用中不断地划分数组直到最小的时候两两进行划分和合并，合并的时候会改变顺序，然而就是在这时根据左右元素的大小来判断逆序对了，而且在层层的递归划分合并过程中，并不会改变整个左边元素相对右边元素的位置，可以结合下面这张图理解

  可以结合以下示意图理解：

  归并排序示意图

代码

实际就是在归并排序的代码中增加了一个全局变量 resPair, 在merge() 函数比较左右两个数组的元素大小部分的代码中，在左边元素大于右边元素的情况下添加 resPair+=(mid-keftP+1); 以统计逆序对数量,可以在主函数中打印resPair 。

while((leftP<=mid)&&(rightP<=end)){
    if(arr[leftP]<=arr[rightP]){
        tmpArr[i]=arr[leftP];
        i++;
        leftP++;
        //或直接写为 tmpArr[i++]=arr[leftP++];
    }
    else{//左边元素大于右边元素
        tmpArr[i]=arr[rightP];
        i++;
        rightP++; 
        resPair+=(mid-leftP+1);//统计逆序对数量
    }
}

完整代码如下：

#include<iostream>
#include<cstdlib>
using namespace std;

void mergeSort(int* arr,int begin,int end); 
void merge(int* arr,int begin,int mid,int end);

int resPair;

int main(){
    int arr[6]={1,3,2,5,4,7};
    int arrLen=sizeof(arr)/sizeof(arr[0]);
    
    mergeSort(arr,0,arrLen-1);
    
    for(int i=0;i<arrLen;i++){
        printf("%d ",arr[i]);
    }
    return 0;
} 

void mergeSort(int* arr,int begin,int end){
    if(begin<end){//注意这个出口条件，不然会陷入死循环 
        int mid=begin+((end-begin)>>1);
        mergeSort(arr,begin,mid);//两次调用mergeSort分别传入两个区间的参数，相当于不断划分了
        mergeSort(arr,mid+1,end);
        merge(arr,begin,mid,end);//合并
    }
}
/*合并的函数*/
void merge(int* arr,int begin,int mid,int end){
    int len=end-begin+1;//当前划分状态下的数组长度 
    int tmpArr[len];//辅助数组
     
    int leftP=begin;//左指针 
    int rightP=mid+1;//右指针 
    int i=0;//辅助数组当前存取的下标 
    //printf("initial. len=%d\n",len);
    
    while((leftP<=mid)&&(rightP<=end)){
        if(arr[leftP]<=arr[rightP]){
            tmpArr[i]=arr[leftP];
            i++;
            leftP++;
            //或直接写为 tmpArr[i++]=arr[leftP++];注意i++和++i的区别
        }
        else{//左边元素大于右边元素
            tmpArr[i]=arr[rightP];
            i++;
            rightP++; 
            resPair+=(mid-leftP+1);//统计逆序对数量
        }
    }
    while(leftP<=mid){//如果左数组有剩余元素 
        tmpArr[i]=arr[leftP];
        i++; 
        leftP++;
    }
    while(rightP<=end){//如果右数组有剩余元素 
        tmpArr[i]=arr[rightP];
        i++;
        rightP++;
    }
    /*将排序好的辅助数组复制到原数组中，
    因为递归要用到上一层排好序的原数组，并所以这一步必不可少*/ 
    i=0;  
    while(begin<=end){
        arr[begin++]=tmpArr[i++];
    }
    //注意每次递归数组的开始位置不一样，为begin，不一定是0，所以不能用下面的赋值方法 
//  for(i=0;i<len;i++){
//      arr[i]=tmpArr[i];
//  }       

}