Chinaunix首页 | 论坛 | 博客
  • 博客访问: 103797
  • 博文数量: 35
  • 博客积分: 2386
  • 博客等级: 大尉
  • 技术积分: 380
  • 用 户 组: 普通用户
  • 注册时间: 2009-05-05 06:11
文章分类

全部博文(35)

文章存档

2011年(1)

2010年(2)

2009年(32)

分类:

2009-05-15 16:06:38

设A[1...n]是一个包含n个不同数的数组。如果在iA[j],则(i,j)就称为
A中的一个逆序对(inversion)。试确定n个元素的任意排列中逆序对的数目

I   修改合并排序merge sort
    设置计数器,每次交换元素位置时计数器加1
    时间复杂度O(nlgn)

II  
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (a[i] < a[j])
                count++
阅读(371) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~