分治递归逆序数_[模板] 归并排序 逆序数 分治

归并排序

图来自维基

递归调用的过程需要在脑中模拟清楚

然后是代码的细节问题

多复习多理解

刘汝佳版

#include

using namespace std;

const int MAXN = 1e5 + 10;

int ans = 0;

int arr[MAXN] = {0};

int brr[MAXN] = {0};

void mergesort(int *arr, int fst, int lst, int *brr)

{

if(lst - fst > 1)

{

int mid = fst + (lst - fst) / 2;

int p = fst, q = mid, i = fst;

mergesort(arr, fst, mid, brr);

mergesort(arr, mid, lst, brr);

while(p < mid || q < lst)

{

if(q >= lst || (p < mid && arr[p] <= arr[q]))

{

brr[i++] = arr[p++];

}

else

{

brr[i++] = arr[q++];

ans += mid - p;

}

}

for(i = fst; i < lst; i++)

arr[i] = brr[i];

}

}

int main()

{

int n;

cin>>n;

for(int i = 0; i < n; i++)

cin>>arr[i];

mergesort(arr, 0, n, brr);

//for(int i = 0; i < n; i++)

//cout<

cout<

return 0;

}

//正月点灯笼版

#include

using namespace std;

long long ans = 0; //声明逆序数

void merge(int a[], int L, int M, int R)

{

int leftlen = M - L;

int rightlen = R - M + 1;

int left[leftlen];

int right[rightlen];

int i , j , k;

for(i = L; i < M; i++)

{

left[i - L] = a[i];

}

for(i = M; i <= R; i++)

{

right[i - M] = a[i];

}

i = 0; j = 0; k = L;

while(i < leftlen && j < rightlen)

{

if(left[i] < right[j])

{

a[k++] = left[i++];

}

else

{

a[k++] = right[j++];

ans += leftlen - i; //求逆序数

}

}

while(i < leftlen)

{

a[k++] = left[i++];

}

while(j < rightlen)

{

a[k++] = right[j++];

}

}

void merge_sort(int a[], int L, int R)

{

if(L == R)

return ;

else

{

int M = (R + L) / 2;

merge_sort(a, L, M); //递归分解左侧

merge_sort(a, M + 1, R); //递归分解右侧

merge(a,L,M + 1,R); //合并

}

}

int main()

{

ios::sync_with_stdio(false);

int a[50010];

int n;

cin>>n;

for(int i = 0; i < n; i++)

cin>>a[i];

merge_sort(a,0,n - 1);

for(int i = 0; i < n; i++)

{

cout<

}

cout<

cout<

return 0;

}

总结

以上是生活随笔为你收集整理的分治递归逆序数_[模板] 归并排序 逆序数 分治的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。