问题描述：
输入：无序数组
输出：数组中存在的逆序数个数
分析：本题目是在不改变原数组的情况下进行问题求解，可采用朴素算法(暴力求解)和归并算法(分治思想)进行求解。
朴素算法：
int inversions(T arr[],int n)
{
//略
}
采用分治思想进行求解
分治算法思想在于分而治之，按照：分解->计算->合并这个流程进行计算，而计算这个步骤，又可将其进行递归求解，即再分解->再计算->再合并，通过将复杂问题分解成简单问题，再合并计算，能够使算法复杂度降低到nlogn大小。其算法主体部分如下：
template<typename T>
int __inversions(T arr[],int l, int r){
if(l+1 >= r)//递归退出条件
return 0;
//分治
int mid = (l+r)/2;
int li = __inversions(arr, l, mid,type);
int ri = __inversions(arr, mid, r,type);
return li+ri+__merge(arr,l,mid,r);//合并
}
//求解函数
template<typename T>
int inversions(T arr[],int n)
{
// SortTestHelper::copyIntArray函数，是对原有数组进行copy
//防止在归并过程中，对原数组组成破坏
T* temp = SortTestHelper::copyIntArray(arr, n);
int result = __inversions(temp, 0, n);
delete[] temp;
return result;
}
其中函数__merge(arr,l,mid,r)为核心算法部分：
算法1：
每次归并过程中，先将左右子数组进行排序，然后再求解逆序数
#include<algorithm>
template<typename T>
int __merge(T arr[], int l, int mid, int r){
int a_len = mid - l;
int b_len = r - mid;
T* a = SortTestHelper::copyIntArray(&arr[l], a_len);
T* b = SortTestHelper::copyIntArray(&arr[mid], b_len);
sort(a,a+a_len);
sort(b,b+b_len);
int num = 0;
if(a[0] > b[b_len - 1]){
num = a_len * b_len;
}else if(a[a_len - 1] <= b[0]){
num = 0;
}else {
int i=0, j=0;
while(i < a_len && j < b_len){
if(a[i] > b[j]){
num += (a_len-i);
j++;
}else{
i++;
}
}
}
delete[] a;
delete[] b;
return num;
}
算法2:
将原数组逐渐归并，使用插入排序进行计算逆序数，由于每次合并过程中，左右子数组已经有序，故省去了重复排序的过程。
template<typename T>
int __merge(T arr[], int l, int mid, int r){
//对于数组arr，其[l,mid)和[mid,r)内的子数组已有序
//然后分情况讨论
///情况1:[l,r)范围内数组都有序
if(arr[mid-1]<=arr[mid])
return 0;
///情况2:[l,mid)全部大于[mid,r)
if(arr[l]>arr[r-1]){
__inv(arr,l,mid,r);
return (mid-l)*(r-mid);
}
///情况3:在[l,r)范围中，由于两个子数组[l,mid)和[mid,r)分别有序，故可采用插入排序思想进行计算合并的逆序数
int num = 0;
for(int i=mid; i<r; i++){
T e = arr[i];
int j;
for(j=i; j>l && arr[j-1]>e; j--){
arr[j]=arr[j-1];
num++;
}
arr[j]=e;
}
return num;
}
算法3:
用空间效率换来时间效率，采用归并进行求解。
template<typename T>
int __merge(T arr[], int l, int mid, int r){
//对于数组arr，其[l,mid)和[mid,r)内的子数组已有序
//然后分情况讨论
///情况1:[l,r)范围内数组都有序
if(arr[mid-1]<=arr[mid])
return 0;
///情况2:[l,mid)全部大于[mid,r)
if(arr[l]>arr[r-1]){
__inv(arr,l,mid,r);
return (mid-l)*(r-mid);
}
///情况3:在[l,r)范围中，通过寻找最小数组[l,min)，和最大数组[max,r)，缩小求解范围
///只需求得[min,max)中逆序数即可
int min=l,max=r;
// while(arr[min] <= arr[mid])
// min++;
// while(arr[max-1] >= arr[mid-1])
// max--;
int a_len = mid - min;
int b_len = max - mid;
T* a = SortTestHelper::copyIntArray(&arr[min], a_len);
T* b = SortTestHelper::copyIntArray(&arr[mid], b_len);
int num=0, i=0, j=0;
for(int k=min; k<max; k++){
if(i >= a_len){
///这里不需要copy的原因是，当a结束时，b剩余的[j,b_len)的子数组与原arr[k,max)相同
//copy(b+j,b+b_len,arr+k);
break;
}
else if(j >= b_len)
{
copy(a+i, a+a_len, arr+k);
break;
}
else if(a[i] > b[j]){
arr[k] = b[j];
num += (a_len-i);
j++;
}else{
arr[k] = a[i];
i++;
}
}
delete[] a;
delete[] b;
return num;
}
其中__inv函数，作用是将左右子数组进行交换，虽然mid是当前操作的子数组中点，但并不疑问着左右子数组长度相等，故需要考虑越界问题。
//将左右子数组进行替换
template<typename T>
void __inv(T arr[], int l, int mid, int r){
int l_len = mid-l;//左子数组长度
T* temp = SortTestHelper::copyIntArray(&arr[l], l_len);
copy(arr+mid,arr+r,arr+l);
copy(temp, temp+l_len, arr+(r-l_len));
delete[] temp;
}
结果
测试数据为10000000个不重复顺序数组，随机交换10000000次。
结果如图：
image.png
网友评论