C语言问题

Question

给一个序列,求逆对.
要求用快速排序算法实现.给出核心算法即可,高手请进.要的是快速算法.
是逆对!例如{4,3,5,2}序列的逆对为{4,3}{3,2}{5,2}
逆对个数为3个.

Answer 1

算法：分治法
数据结构：数组
步骤：
(1)把数组从中间分为两段；
(2)递归调用此算法，分别处理前半段和后半段，分别得出前 半段和后半段的捣乱个数，并排序前半段和后半段；
(3)再计算前半段大于后半段的次数；
(4)三个结果相加，得出捣乱总数。
伪代码：
Count_inver(L)
{
If (只有一个元素) return 0;
Else {
Devide L into two lists, A, B;/*A :0~n/2, B: 1＋n/2～n-1*/;
Ra = count_inver(A);
Rb = count_inver(B);
Rm = merge(A, B);
Return (Ra+Rb+Rm);
}
}
Merge的实现：
由于A，B已经升序排序完毕，可以这样计算出”AB之间”的的捣乱数目。仿照归并排序的merge过程，把AB归并为一个有序数组,供下一轮递归调用，在归并的过程中，每放入一个A元素，都统计这个元素大于B数组的个数，归并完毕后可得Rm。这个merge的过程可以在O(n)时间内完成。
算法复杂度分析：
T(n) = 2T(n/2)+O(n)，得O(n*logn)

//你的例子4,3,5,2中，(4,3)(4,2)(3,2)(5,2)都是
//需要代码的话，给我消息。

Answer 2

那{4,5}{4,2}{3,5}为什么就不是呢
逆对的定义是什么？

Answer 3

逆对是不是就是从大到小的排列？如果是的话，那么你可以用冒泡排序法：
for(i=0;i<MAX-1;i++)/*其中的序列是在数组里面存着的，而MAX是它的数组小标的最大值*/
for(j=i+1;j<MAX;j++)
{
int m;
if(s[i]<s[j]) /*s为数组名*/
{
m=s[i];
s[i]=s[j];
s[j]=m;
}
}
实在是搞不懂你的逆对是什么意思～～ 你最好写明白一点

Answer 4

既然是对，那就只有两个，用个for循环暴搜就行了
int s[4]={4,3,5,2};
int count=0;
int i,j;
for(i=0;i<4;i++)
for(j=i+1;j<4;j++)
if(s[i]>s[j]) count++;
printf("%d\n",count);
我没有调试程序应该没问题。