犀牛云做网站如何网络服务提供者知道或者应当知道网络用户利用其网络

犀牛云做网站如何,网络服务提供者知道或者应当知道网络用户利用其网络,html代码图片,开发一款社交app需要多少钱这次#xff0c;我来分享一下我新学习的归并排序#xff01; 1311#xff1a;【例2.5】求逆序对 网上有很多大佬整理了归并排序#xff0c;并且超级厉害的做了动图。就是这个大佬努力的老周的排序——归并排序#xff08;Merge sort#xff09; 下面我想回顾总结一下我…这次我来分享一下我新学习的归并排序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] 在i1······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 lr1 ; merge_sort(q,l,mid) ; merge_sort(q,mid1,r) ; int i l , j mid1 , 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 ; }