首页 > 代码库 > 归并排序&&逆序对(codves1688,4163)

归并排序&&逆序对(codves1688,4163)

归并排序

归并排序采用的是分治的思想

1、划分问题:把序列分为元素个数尽量相等的两半

2、递归求解:把两半分别排序

3、合并问题:把两个有序的序列合并为一个

对于第三个问题,我们可以从两个序列中最小的元素开始比较,把较小的加入新的队列中,直到某个序列为空,把另外的一个序列直接加入,然后将原来的序列覆盖。其实很简单,下面看看模板代码

 技术分享

 写得烂,不要在意(⊙o⊙)…;

这个就是归并排序(⊙o⊙)…,本人感觉很简单的,归并排序好像比sort,快排的复杂度低,也就是说快一点,是NlogN的复杂度。既然说了归并排序,就不得不说下逆序对如codevs 1688 模板题

1688 求逆序对

题目描述 Description

给定一个序列a1,a2,…,an,如果存在i<j并且ai>aj,那么我们称之为逆序对,求逆序对的数目

!!!!!!数据范围:N<=105。Ai<=105。时间限制为1s。//注意这里范围

 输入描述 Input Description

第一行为n,表示序列长度,接下来的n行,第i+1行表示序列中的第i个数。

输出描述 Output Description

所有逆序对总数.

样例输入 Sample Input

4

3

2

3

2

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint
  
    对于逆序对如果范围小,可以用冒泡排序,交换一次ans++;最后排好了答案就出来了。但是冒泡排序是O(n^2)的复杂度,一看数据范围是1e5
就知道要超时。所以就用归并排序,来实现问题。其实只需要加一句代码就行了
技术分享
  
    加上这句就完啦,最后输出ans就可以了。
    为什么是加mid-q+1呢?

       我们在进行合并的时候是从小到大进行的,就是说,当把右段的数x放到临时数组t中的时候,左段的数一定比x都大,有 mid-p+1个,这些数一定都和x成逆序对,因为他们的位置在x前,而值比x大。

      这就是逆序对的解法。

 

 

归并排序&&逆序对(codves1688,4163)