归并排序

原理

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并操作

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
如　设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8,1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4
第三次归并后：{1,6,8,38,100,202,301},比较次数：4
总的比较次数为：3+4+4=11
逆序数为14

用途

求逆序对 http://luo.hustoj.com/problem.php?cid=1174&pid=6

求交换次数 http://luo.hustoj.com/problem.php?cid=1196&pid=2

#include <bits/stdc++.h>
using namespace std;

int a[500005],tmp[500005];
long long ans=0;

void ms(int l,int r){
  int mid;
  if (l==r) return;
  mid=(l+r)/2;
  ms(l,mid);
  ms(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];
      k++;
      i++;
    }else{
      tmp[k]=a[j];
      ans+=mid-i+1;  //逆序对数【交换次数】
      k++;
      j++;
    }
  }
  while (i<=mid){
    tmp[k]=a[i];
    k++;
    i++;
  }
  while (j<=r){
    tmp[k]=a[j];
    k++;
    j++;
  }
  for (int i=l;i<=r;++i){
    a[i]=tmp[i];
  }
}

int main(){
  int n;
  cin>>n;
  for (int i=1;i<=n;++i){
    scanf("%d",&a[i]);
  }
  ms(1,n);
  cout<<ans;  //逆序对数【交换次数】
  return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/23/