（算法导论习题解problem2.4）寻找一个序列中逆序对的数量

（算法导论习题解problem2.4）寻找一个序列中逆序对的数量2010-06-09 C++博客那谁一个序列的逆序对是这样的两个元素, 对于序列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（"
"）;
}

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
",count_inversion（array, 0, 4））;

    display（array, 5）;

    return 0;
}