《算法设计与分析》实验报告1
《算法设计与分析》实验报告1
实验名称: 统计一个排列中逆序对的个数
系 别:xxx
专 业:xxx
班 级:xxx
姓 名:xxx
学 号:xxx
实验日期:xx年xx月xx日
1. 算法题目
统计一个排列中逆序对的个数
2. 设计思路与步骤
通过归并排序,在排序的过程中统计逆序的的个数。
3. 算法实现与代码
#include<stdio.h>
int num=0;
void Merge(int *A,int *B,int first,int m,int end);
void Inversion(int *A,int *B,int first,int end);
int main(){
int i,n;
int A[100];
int B[100];
printf("请输入要排序的个数;");
scanf("%d",&n);
for(i=1;i<=n;i++){
printf("请输入要排序的元素:\n");
scanf("%d",&A[i]);
}
Inversion(A,B,1,n);
for(i=1;i<=n;i++){
}
printf("逆序对个数为:%d",num);
}
void Inversion(int *A,int *B,int first,int end){
if(first<end){
int m, i;
m=(first+end)/2;
Inversion(A,B,first,m);
Inversion(A,B,m+1,end);
Merge(A,B,first,m,end);
for(i=first;i<=end;i++){
A[i]=B[i];
}
}
}
void Merge(int *A,int *B,int first,int m,int end){
int i=first;
int j=m+1;
int k=first;
while(i<=m&&j<=end){
if(A[i]<=A[j]){
B[k++]=A[i++];
}
else{
B[k++]=A[j++];
num+=m-i+1;
}
}
while(i<=m){
B[k++]=A[i++];
}
while(j<=end){
B[k++]=A[j++];
}
}
4. 测试用例与结果

5. 问题与总结:
答:xxx。