英文二手汽车网站建设,qq免费搭建网站,网站销售系统怎么做,济南seo关键词优化方案文章目录 1.归并排序1.1 递归版本1.2 非递归版本 2.归并分治2.1 计算数组的小和2.2 计算翻转对 1.归并排序
归并排序的核心步骤是#xff1a;
拆分#xff1a;将无序数组不断对半拆分成小块#xff0c;直到每个小块只剩一个元素#xff08;自然有序#xff09;。 合并
拆分将无序数组不断对半拆分成小块直到每个小块只剩一个元素自然有序。 合并将相邻的有序小块合并逐步形成更大的有序块直到整个数组有序。
1.1 递归版本
递归天然避免越界代码简洁但递归深度受限。
#include vector
using namespace std;// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right)
{vectorint temp(right - left 1); // 临时数组int i left, j mid 1, k 0;// 双指针合并有序区间while (i mid j right) {temp[k] (arr[i] arr[j]) ? arr[i] : arr[j];}// 处理剩余元素while (i mid) temp[k] arr[i];while (j right) temp[k] arr[j];// 拷贝回原数组for (int p 0; p k; p) {arr[left p] temp[p];}
}// 递归归并排序
void mergeSort(int arr[], int left, int right) {if (left right) return;int mid left (right - left) / 2;mergeSort(arr, left, mid);//分解左半区mergeSort(arr, mid 1, right);//分解右半区merge(arr, left, mid, right);//合并有序区间
}int main()
{int arr[] {12, 11, 13, 5, 6, 7};int n sizeof(arr)/sizeof(arr[0]);mergeSort(arr, 0, n-1);return 0;
}1.2 非递归版本
非递归版本通过步长控制把数组看作由多个有序子数组组成逐步扩大子数组长度直到整个数组有序。 非递归循环效率更高适合大数据量但是需要控制越界。
与递归版本不同的是递归是自顶向下通过递归函数先拆分再合并非递归是自底向上通过数组下标直接从小块开始合并
假设原始数组为 [3,1,4,2,7,5] 执行步骤如下 步长1把每个元素视为独立的有序数组两两合并→ 合并后 [1,3] [2,4] [5,7] 步长2合并相邻的两个长度为2的子数组→ 合并后 [1,2,3,4] [5,7] 步长4继续合并更大的子数组→ 最终得到 [1,2,3,4,5,7]
void mergeSort(int arr[], int n)
{// 预分配临时空间vectorint temp(n); // 按步长分组1,2,4,8...for (int gap 1; gap n; gap * 2) {// 每两组进行比较 //[left, leftgap-1] [leftgap,left2*gap-1]//[left,mid][mid1, right]for (int left 0; left n; left 2*gap) {// 计算子数组边界 (按l,m,r)int mid min(left gap - 1, n-1);int right min(left 2*gap - 1, n-1);// 合并相邻子数组int i left, j mid 1, k left;while (i mid j right) {temp[k] (arr[i] arr[j]) ? arr[i] : arr[j];}// 处理剩余元素while (i mid) temp[k] arr[i];while (j right) temp[k] arr[j];// 拷贝回原数组for (int p left; p right; p) {arr[p] temp[p];}}}
}int main()
{int arr[] {12, 11, 13, 5, 6, 7};int n sizeof(arr)/sizeof(arr[0]);mergeSort(arr, n);return 0;
}2.归并分治
实施原理
思考问题在大范围的答案是否等于左部分的答案右部分的答案跨越左右部分的答案。计算跨越左右部分的答案时如果左右部分各自有序是否能让计算跨越左右部分答案时更加便利。
分治法的基本步骤
分解将原始数组通过递归的方式拆分成两个长度相近的子数组一直拆分到单个元素为止因为单个元素天生有序统计根据题意进行相关的统计。排序根据题意思考在将小部分合并成大部分之前如果将小部分进行排序是否能便于大部分进行统计。 2.1 计算数组的小和
计算数组的小和 首先让我们看一组示例 [135246]这个小和答案为27其暴力解法很好想就是每个数和其他的数进行比较进行累加但时间复杂度是O(n^2)所以不考虑。 下面看看这题归并分治的解法。 1. 根据上面说的原理我们先看整个大范围部分[135246]的答案是否可以通过左部分[135]加上右部分[246]再加上跨越左右的答案。 首先我们直接计算[135]小和是5[246]小和是8。接下来计算跨越左右的答案[135] | [246]可以看到两边内部的已经各种计算好了那么跨越的先看2对应的21再23那么对应2的小和就只有1。再看4对应的41,43,45那么4对应的小和就是46类推就是9那么跨越的小和加起来就是14再和前面相加1458就是27答案对应上了。 2. 那么如果再把大范围缩小到计算[1,3,5]的答案可以看出其左部分[1,3]小和为1右部分[5]小和为0跨越左右为4相加后也对应上了小和为5。那么就可以看出小部分的解和大部分的解都是一样的那么就可以考虑归并分治。 3.接下来考虑在计算跨越左右的答案时如果左、右部分各自有序这个条件计算会不会更简单。 我们看[135] | [246]如果其未排序[3,1,5] [6,2,4]那么对于未排序的计算需要每个数和其他数进行比较累加就是暴力解法。肯定是更复杂的。 4.那么这道题保持左右各有序后计算便利在哪 比如这个例子[3,6,7] [5,6,9]在计算跨越左右的答案时有两种算法。 1从右部分开始对左部分的数进行比对对应5大于3对应63,66对应93,96,97我们可以发现右部分下一个数的计算(如5之后的66之后的9)可以在上一个数的基础上继续计算并且加上上一个数的和。 具体什么意思就是比如右部分的5在和左部分3比较后再和左部分6比较由于56那么左部分就到6停下一个右部分的6直接和左部分的6进行比较再和7比较然后停。右部分6的小和就直接加上5的小和和比较的6。右部分的9就直接加上6的小和以及比较的7。这样就不用右部分每一个数都和左边的比了因为有序 2从左部分开始对右部分的数进行比对如果5大于3那么5后面所有的数都大于3就直接3乘以5以及右边的个数就行了。 两个方法时间复杂度都是O(N)相当于把每个数都走了一遍。 对应从右部分开始对左部分的数进行比对
//代表整个跨左右的答案
long long ans 0;
//先固定右部分的数sum代表每个数自己的小和
for(int j m1, i l, sum 0; j r; j)
{//每个数的小和 这一回的比较 上一个数的小和while(i m s[i] s[j]) sums[i];ans sum;
}对应从左部分开始对右部分的数进行比对
//代表整个跨左右的答案
long long ans 0;
for(int j m1, i l; j r; j)
{while(i m s[i] s[j]){ans(r-j1)*s[i];i;}
}完整代码
#include iostreamusing namespace std;const int MAXN 100001;int s[MAXN];
int tmp[MAXN];long long Merge(int l, int m, int r)
{//1.先统计long long ans 0;for(int j m1, i l, sum 0; j r; j){while(i m s[i] s[j]) sums[i];ans sum;}/*//计算方法二long long ans 0; for(int j m1, i l; j r; j){while(i m s[i] s[j]){ans(r-j1)*s[i];}}*///2.再排序方便后续部分的统计int i l, k l, j m1;while(i m j r){tmp[k] (s[i] s[j] ? s[i] : s[j]);}while(i m) tmp[k] s[i];while(j r) tmp[k] s[j];for (int i l; i r; i){s[i] tmp[i];}return ans;
}long long Count(int l, int r)
{if(l r) return 0;int m (lr) 1;//接下来进行细分同时统计计算再排序return Count(l, m) Count(m1, r) Merge(l, m, r);
}int main() {int n 0;while(cin n){for(int i 0; i n; i) cins[i];//首先对数组进行细分cout Count(0, n-1) endl;}return 0;
}2.2 计算翻转对
计算翻转对 还是照着之前说的原理拿[2,4,3,5,1]分成两个部分[2,4,3] [5,1]在假设两个部分分别计算好翻转对数量以及排序后[2,4,3] 有0个翻转对[5,1]是1个统计完后因为各个内部翻转对已经计算好了然后想排序后对于两边跨越的计算是否更便利答案是肯定的各自排序后。那么计算跨越左右的[2,3,4][1,5]也是有两种方法简单的法一3大于1*2了那么排序后3之后都是大于3的也就是都能和1能组成翻转对的。法二3和1比完后接着4和5比然后再加上3对应的翻转对数。因为3满足的4也满足。
class Solution {
public:int tmp[50001] {0};int Merge(vectorint nums, int l, int m, int r){//1.统计int ans 0;//法一// for(int i l, j m1, count 0; i m; i)// {// while(j r nums[i] (long)2*nums[j]) count, j;// ans count;// }//法二for(int i l, j m1; i m; i){while(j r nums[i] (long)2*nums[j]){ans (m-i1);j;}}//2.排序int a l, b l, c m1;while(a m c r){tmp[b] (nums[a] nums[c] ? nums[a] : nums[c]);} while(a m) tmp[b] nums[a];while(c r) tmp[b] nums[c];for(int i l; i r; i) nums[i] tmp[i];return ans;}int Count(vectorint nums, int l, int r){if(l r) return 0;int m (lr) 1;return Count(nums, l, m) Count(nums, m1, r) Merge(nums, l, m, r);}int reversePairs(vectorint nums) {int len nums.size();return Count(nums, 0, len-1);}
};算法中有很多精妙又美丽的思想传统请务必坚持下去
