归并排序的知识

一.什么是归并排序归并排序是一种基于分治思想的高效稳定的排序算法是算法竞赛中非常常用的排序方法也是求逆序对的经典算法二.归并排序的核心思想核心思想是分治思想分而治之它的流程可以拆分为3步1.分把待排序的数组从中间一分为二递归地左右两个子数组接着拆分直到每个子数组只有一个元素天然有序2.治递归地对左右两个子数组进行排序3.合把两个已经排好序的子数组合并成一个完整的有序数组三.如何实现归并排序以mergel,r为例1.递归终止条件if(lr) return ;当区间只有一个元素时lr或者区间非法lr时直接返回不需要排序2.分拆成两半int mid(lr)/2;merge(l,mid);merge(mid1,r);先递归把左半段【lmid】排好序再递归把右半段【mid1r】排好序。递归到底层后左右两端都是有序数组3.合合并两个有序数组核心int il,jmid1,kl;while(imidjr){if(a[i]a[j])tmp[k]a[i];else{tmp[i]a[j];ansmid-i1;}}两个指针ij分别指向左右两端的开头k指向临时数组tmp的写入位置每次把两个指针指向的较小值写入tmp若a【i】a【j】说明a【i】a【j】不会产生逆序对直接写入tmp若a【i】a【j】说明a【j】比左半段从i到mid的所有元素都小会产生mid-i1个逆序对写入tmp并更新ans4.收尾拷贝剩余元素while(imid) tmp[k]a[i];while(jr) tmp[k]a[j];for(int pl;pr;p)a[p]tmp[p];把左右两端中剩下的元素直接写入tmp把tmp中合并好的有序数组拷贝回原数组a供上一层递归使用四.完整可运行代码#include bits/stdc.husing namespace std;const int N 500010;int a[N], tmp[N];long long ans 0; // 逆序对数量可能很大必须用long long void merge(int l, int r){if(l r) return;int mid (l r) /2;merge(l, mid);merge(mid 1, r);int i l, j mid 1, k l;while(i mid j r){ if(a[i] a[j]){ tmp[k] a[i]; }else{ tmp[k] a[j];ans mid - i 1; // 统计逆序对 } }while(i mid)tmp[k] a[i];while(j r) tmp[k] a[j];for(int p l; p r; p) a[p] tmp[p];}int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin n;for(int i 1; i n; i){cin a[i];}merge(1, n);cout ans endl;return 0; }