一個序列的逆序對是這樣的兩個元素, 對于序列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 %d\n",count_inversion(array, 0, 4));
display(array, 5);
return 0;
}