逆对编程

来源：百度知道 编辑：UC知道 时间：2024/06/20 04:26:39
1. 统计一个序列中逆对的个数。
给定一个序列X = {a1, a2, …, an}, X中的一对元素(ai,aj) 称为逆对如果 i<j 且 ai>aj. 例如，序列{5, 3, 6, 4, 2, 3}具有10个逆对: (5,3), (5,4), (5,2), (5,3), (3,2), (6,4), (6,2), (6,3), (4,2), (4,3).
你的程序应该对任意从文件中输入的整数序列，统计出逆对的个数. 要求至少能够计算1万个元素的序列.

int _inv_pair(int list[], int length) {
if(length == 0) return 0;
else {
int toReturn = 0;

for(int i = 1; i < length; i++) {
if(list[i] < list[0]) toReturn++;
}

return toReturn + _inv_pair(&list[1], --length);
}
}

#include "stdio.h"
//假设整数序列存放在数组a[maxsize]中;并且len指出其整数的个数;
main()
{long i,j,k=0,a[maxsize];
for(i=0;i<len-1;i++)
{for(j=i+1;j<len;j++)
if(a[i]>a[j]) k++;}
printf("k=%ld",k);
}