那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

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

一个序列的逆序对是这样的两个元素, 对于序列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 *= (int *)malloc((llen + 1* sizeof(int));
    
int *= (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, 04));

    display(array, 
5);

    
return 0;
}



posted on 2008-09-29 20:32 那谁 阅读(3072) 评论(1)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: (算法导论习题解problem2.4)寻找一个序列中逆序对的数量  回复  更多评论   

merge_inversion的时候:
L和H两个数据必须有序吧?
2012-09-20 13:53 | 1231

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理