一个序列的逆序对是这样的两个元素, 对于序列A而言, i>j且A[i]<A[j], 于是A[i]和A[j]就形成一个逆序对.

　　研究一个序列中逆序对的数量是有实际意义的, 对于插入排序而言, 它排序的时间与待排序序列的逆序对数量成正比.

　　下面给出求出一个序列中逆序对数量的算法,类似于归并排序中使用的分治算法:一个序列的逆序对数量为它的左半部分逆序对的数量,加上右半部分逆序对的数量, 最后在合并的时候左半部分元素大于右半部分元素的数量.这几乎和归并算法的过程一模一样,只是在归并的时候加入了计数的操作, 完整的算法为:

#include <stdio.h>

void display(int array[], int size)
{
　　　 int i;
　　　 for (i = 0; i < size; ++i)
　　　 {
　　　　　　　 printf("%d ", array[i]);
　　　 }

　　　 printf("n");
}

int merge_inversion(int array[], int low, int middle, int high)
{
　　　 int count = 0;
　　　 int llen = middle - low + 1;
　　　 int hlen = high - middle;
　　　 int *L = (int *)malloc((llen + 1) * sizeof(int));
　　　 int *H = (int *)malloc((hlen + 1) * sizeof(int));
　　　 int i, j, k;

　　　 for(i = 0; i < llen; i++)
　　　　　　　 L[i] = array[low + i];
　　　 L[i] = 99999;
　　　 for(i = 0; i < hlen; i++)
　　　　　　　 H[i] = array[middle + i + 1];
　　　 H[i] = 99999;

　　　 for(i = 0, j = 0, k = low; k < high + 1; k++)　　
　　　 {
　　　　　　　 if(L[i] > H[j])
　　　　　　　 {
　　　　　　　　　　　 array[k] = H[j++];
　　　　　　　　　　　 count += llen - i;
　　　　　　　 }
　　　　　　　 else
　　　　　　　 {
　　　　　　　　　　　 array[k] = L[i++];
　　　　　　　 }
　　　 }

　　　 free(L);
　　　 free(H);

　　　 return count;
}

int count_inversion(int array[], int low, int high)
{
　　　 int count = 0, middle;
　　　 if(low < high)
　　　 {
　　　　　　　 middle = low + (high - low) / 2;
　　　　　　　 count += count_inversion(array, low, middle);
　　　　　　　 count += count_inversion(array, middle + 1, high);
　　　　　　　 count += merge_inversion(array, low, middle, high);
　　　 }

　　　 return count;
}

int main()
{
　　　 int array[]={2,8,3,6,1};
　　　 printf("count of inversions is %dn",count_inversion(array, 0, 4));

　　　 display(array, 5);

　　　 return 0;
}