之前看到的给定有序表A[1:n],修改合并排序算 - 已解决

之前看到的给定有序表A[1:n],修改合并排序算法,求出该有序表的逆序对数?的回答

我想知道那么,可以先递归地对left和right做归并排序,同时顺便求出它们的逆序对数.这个怎么实现?

如果能求出其中一组的逆序对数,为什么要分成两组呢?

我的问题好白痴.感觉没问到点子上啦- -

收藏：

点赞数：

评论数：

1个回答

怎么实现的,你百度一下,网上一堆源码,我这么打字给你说一时半会儿也说不清楚.有需要的话加我详聊.

为什么要分成两组?好吧这个问题问的好.

你想一下归并排序为什么要分成两组.首先,这是分治思想.可能你会疑惑为什么分治就能降低复杂度.如果只单纯的看合并两个排好序的数组的复杂度只要O（n）.同样的,计算数组left部分和right部分之间构成的逆序对也只要O（n）的复杂度.一层一层这么分下去,每一层都只需要完成一个合并就可以了,所以总的复杂度才会是O（n＊logn）.明白了么?

点赞数：

评论数：

相关问题

9.在待排序的数据表已经为有序时,下列排序算法中花费时间反而多的是（　　）

点赞数：
0
回答数：
1
设顺序表L是一个递减有序表,试写一算法,将x插入其后仍保持L的有序性.

点赞数：
0
回答数：
1
数据结构的问题,关于有序表的有一个有序表为{2,7,9,12,32,40,42,43,64,69,78,80,96,12

点赞数：
0
回答数：
1
对一组无序数据,①设计直接插入排序算法；②再对得到的有序序列进行折半查找.

点赞数：
0
回答数：
1
若m,n∈正整数,试求出所有有序整数对（m,n）,使得(n^3+1)/(mn-1)∈整数

点赞数：
0
回答数：
1
195.将两个各有N个元素的有序表归并成一个有序表,其最少的比较次数是 ( ).为什么答案是n不是1啊、、

点赞数：
0
回答数：
1
将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是多少次?

点赞数：
0
回答数：
1
两个含有N个元素的有序表归并成一个有序表,最少的比较次数又是多少呢?

点赞数：
0
回答数：
1
求两个不等长有序数组的中位数!已知两个有序数组A和B分别有n1和n2个数字,求一个用O（logn1+logn2)的算法去

点赞数：
0
回答数：
2
求数组A和数组B的交集有两个有序数组A和B,请设计算法,求出数组A和数组B的交集.要求：1、请注意是有序2、能否设计时间

点赞数：
0
回答数：
1

关注公众号

一起学习，一起涨知识