笨人小白的温故知新——排序（1）

这次，我来分享一下我新学习的归并排序！

1311：【例2.5】求逆序对

网上有很多大佬整理了归并排序，并且超级厉害的做了动图。就是这个大佬努力的老周的排序——归并排序（Merge sort）

下面我想回顾总结一下我现在对归并排序的认识与理解，并且把它融入这道题中。

我对归并排序的认识：

void merge_sort(int a[], int l, int r) { if (l >= r) return; int mid = l + r >> 1; merge_sort(a, l, mid); merge_sort(a, mid + 1, r); int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) if (a[i] <= a[j]) tmp[k ++ ] = a[i ++ ]; else tmp[k ++ ] = a[j ++ ]; while (i <= mid) tmp[k ++ ] = a[i ++ ]; while (j <= r) tmp[k ++ ] = a[j ++ ]; for (i = l, j = 0; i <= r; i ++, j ++ ) a[i] = tmp[j]; }

这是一段归并排序的模板，由“反复调用merge_sort()函数”和“分治”的过程组成。

在讲述这两个部分之前，我要“前情提要”一下，在进行之前，请在你的脑海里，想像一串数组里的每一个元素被单独放在一个格子里。

（一）“反复调用merge_sort()函数”

1）拆分：这个作用就是将这个连在一起的数组，逐渐拆分成一个一个的小方块。

2）按顺序重组：那么，已经无法再拆的时候，我们如何“浪子回头”，将这些方块重新按顺序拼在一起呢？这时，我们就要设置一个返回条件！也就是if (l >= r) return;

（二）分治过程

分治的过程就是把“对一大串数字进行排序”转换为“对一小部分数字分别进行排序后，再整块进行排序”。这样话可以缩短时间。

定义一个i和j，当作指针，将数组中的数字按照从小到大的顺序进行排序。（这一步我真的心里明白，但是心有余力不足，很难表述出来）

至于为什么会有两行while，那是因为，在排列的时候，会出现左边的几个数字会大于右边的数字，导致右边都进行完了，而左边还会剩下数字（同理，右边也会剩下数字）。

而这道题，则是在归并排序的基础上，多加了一个计数的过程。

那么，现在要考虑的问题有2个：

question1：这个计数sum要加在哪里？

question2：计数运算是怎样的？

第一个问题很好解决，sum肯定要加在出现a[i] > a[j]的情况下面。

第二个问题就需要结合分治的过程，确定这个sum怎么加。因为每一整块都进行过排序，所以，只要发现一个a[i] > a[j] ， 在i+1······mid之间的数字都会大于a[j] ，所以要加上mid - i + 1 。

下面献上这道题的AC代码：

#include <iostream> #include <algorithm> #include <stdio.h> using namespace std ; long long sum = 0 ; int tmp[100005] ; void merge_sort(int q[] , int l , int r){ if(l >= r) return ; int mid = l+r>>1 ; merge_sort(q,l,mid) ; merge_sort(q,mid+1,r) ; int i = l , j = mid+1 , k = 0 ; while(i <= mid && j <= r){ if(q[i] <= q[j]) tmp[k++] = q[i++] ; else{ tmp[k++] = q[j++] ; sum += mid - i + 1 ; } } while(i <= mid) tmp[k++] = q[i++] ; while(j <= r) tmp[k++] = q[j++] ; for(i = l , j = 0 ; i <= r ; i ++ , j ++) q[i] = tmp[j] ; } int main(){ int n , a[100005]; scanf("%d" , &n) ; for(int i = 1 ; i <= n ; i ++) scanf("%d" , &a[i]) ; merge_sort(a , 1 , n) ; printf("%lld" , sum) ; return 0 ; }