2. 归并排序
2.1 思想
- 确定分界点 a[(l+r)/2]
- 递归排序左右
- 归并,合二为一(*)
2.2 算法模板
1 |
|
1 | //测试 |
2.3 练习
2.3.1 逆序对的数量
给定一个长度为 n的整数数列,请你计算数列中的逆序对的数量。(24194中2在1前面,且2>1,所以2和1构成一个逆序对)
输入格式:第一行包含整数 n,表示数列的长度。第二行包含 n个整数,表示整个数列。
输出格式:输出一个整数,表示逆序对的数量。
数据范围:$1≤n≤100000$,$1≤数列中元素的值≤10^9$
输入样例:
1
26
2 3 4 5 6 1输出样例:
1
5
解1
基于归并排序的解法,对于一个逆序对ab分为三种情况:
ab都在左边
ab都在右边
a在左边b在右边
- 确定分界点 a[(l+r)/2]
- 递归排序左右
- 左+右+左右(当a[i]>a[j]时,a[i]后面的数都大于a[j])
1 |
|