// 算法.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#define INFINITE 100000
using namespace std;
int MERGE_INVESTIONS(int a[],int p,int q,int r);
int COUNT_INVERSIONS(int a[],int p,int r);
int main()
{
int a[5]={5,4,3,2,1};
cout<<"\nthe inversion is:"<<COUNT_INVERSIONS(a,0,4)<<endl;
return 0;
}
int MERGE_INVERSIONS(int a[],int p,int q,int r)
{
int n1=q-p+1;
int n2=r-q;
int *L=new int [n1+1];
int *R=new int [n2+1];
int i,j,k;
for(i=0;i<n1;i++)
L[i]=a[p+i];
for(j=0;j<n2;j++)
R[j]=a[q+j+1];
L[n1]=INFINITE;
R[n2]=INFINITE;
i=0,j=0;
int inversion=0;
for(k=p;k<=r;k++)
{
if(L[i]<=R[j])
{
a[k]=L[i];
i++;
}
else
{
a[k]=R[j];
for(int s=i;s<n1;s++)
cout<<"("<<L[s]<<","<<R[j]<<")"<<" ";
j++;
inversion+=n1-i;
}
}
return inversion;
}
int COUNT_INVERSIONS(int a[],int p,int r)
{
int q,inversion=0;
if(p<r)
{
q=(p+r)/2;
inversion+=COUNT_INVERSIONS(a,p,q);
inversion+=COUNT_INVERSIONS(a,q+1,r);
inversion+=MERGE_INVERSIONS(a,p,q,r);
}
return inversion;
}
根据提供的代码文件，我们可以分析出该程序主要实现了对数组中逆序对数量的计算，并采用分治策略进行处理。下面将详细解释代码中的关键概念、算法思路及其具体实现。
### 关键概念
#### 逆序对
在数组 `a[0…n-1]` 中，如果对于某对索引 `(i, j)`，满足 `i < j` 且 `a[i] > a[j]`，则称这对索引为数组的一个逆序对。逆序对的数量可以用来衡量一个序列的有序程度。
### 算法思路
该程序使用了分治法来计算逆序对的数量，主要包括以下三个步骤：
1. **分割**：将数组分为两半。
2. **递归解决子问题**：递归地计算左右两半数组中的逆序对数量。
3. **合并解决子问题的结果**：在合并过程中计算跨两个子数组的逆序对数量。
### 代码解析
#### 主函数 `main`
```cpp
int main()
{
int a[5]={5,4,3,2,1};
cout<<"\nthe inversion is:"<<COUNT_INVERSIONS(a,0,4)<<endl;
return 0;
}
```
主函数初始化了一个包含逆序的数组 `a`，并调用 `COUNT_INVERSIONS` 函数计算逆序对总数。
#### 函数 `COUNT_INVERSIONS`
```cpp
int COUNT_INVERSIONS(int a[],int p,int r)
{
int q,inversion=0;
if(p<r)
{
q=(p+r)/2;
inversion+=COUNT_INVERSIONS(a,p,q);
inversion+=COUNT_INVERSIONS(a,q+1,r);
inversion+=MERGE_INVERSIONS(a,p,q,r);
}
return inversion;
}
```
此函数是递归计算逆序对的核心。首先检查数组是否只有一个元素或为空，如果是，则返回逆序对数量为 0；否则，将数组分为左右两部分，并递归计算左右两部分的逆序对数量，最后通过调用 `MERGE_INVERSIONS` 函数来计算跨越左右两部分的逆序对数量。
#### 函数 `MERGE_INVERSIONS`
```cpp
int MERGE_INVERSIONS(int a[],int p,int q,int r)
{
int n1=q-p+1;
int n2=r-q;
int *L=new int [n1+1];
int *R=new int [n2+1];
int i,j,k;
for(i=0;i<n1;i++)
L[i]=a[p+i];
for(j=0;j<n2;j++)
R[j]=a[q+j+1];
L[n1]=INFINITE;
R[n2]=INFINITE;
i=0,j=0;
int inversion=0;
for(k=p;k<=r;k++)
{
if(L[i]<=R[j])
{
a[k]=L[i];
i++;
}
else
{
a[k]=R[j];
for(int s=i;s<n1;s++)
cout<<"("<<L[s]<<","<<R[j]<<")"<<" ";
j++;
inversion+=n1-i;
}
}
return inversion;
}
```
此函数负责将两个已排序的子数组合并成一个整体，并在合并过程中计算逆序对的数量。它首先创建两个临时数组 `L` 和 `R` 来分别存储左右子数组的数据，并在末尾填充一个无穷大值（`INFINITE`），以确保所有元素都能被正确合并。然后通过比较 `L` 和 `R` 数组中的元素，并将较小者放入原数组中，从而完成合并过程。当遇到从右数组取值时，表示与左数组剩余所有元素构成逆序对，因此统计这些逆序对的数量。
### 总结
这段代码实现了基于分治法的逆序对计数算法，适用于任何整数数组。其核心思想是利用递归来分割问题，并在合并过程中计算逆序对。这种方法不仅简洁高效，而且易于理解和实现。通过本程序的学习，可以帮助我们更好地理解如何运用分治法来解决复杂问题。
