算法15、双指针（归并排序两种做法）
🌰1、two-Sum严格递增序列
晴问算法
因为是有序的序列（严格递增）所以可以考虑用二分查找的思路！
二分查找变体版-双指针。
因为严格递增的序列特性，让i, j(或者left, right)的枚举互相牵制，因而我们可以借由此极大优化算法而不需要再双重循环。
对于二分查找区间【i, j],分别从第一个和最后一个元素开始往中间遍历-->因此i的更新只能++，j的更新只能--：
若a[i]+a[j] == K, 找到了一个解，(现在需要思考如何更新i, j才能找到下一个解-->)则i++j不变（大于K）、i不变j--（小于K）都不会满足，
只有一个变大另一个变小才行，因此剩余的解只会在[i+1, j-1]里产生，于是让 i = i+1; j = j-1;
若a[i]+a[j] > K, 需要让和更小，所以让j = j-1;
若a[i]+a[j] < K, 需要让和更大，所以让i = i+1;
查找区间初值是[0, n-1];
因为题目要求是寻找不同的下标i， j,所以循环结束条件是i == j时，因此进入循环的条件是i < j;
#include <iostream>
using namespace std;
const int MAXN = 100005;
int n, K, a[MAXN];
int twoSum(){
int cnt = 0;
int i = 0, j = n-1;
while(i < j){
if(a[i] + a[j] == K){
cnt ++;
i ++;
j--;
}
else if(a[i] + a[j] > K)
j--;
else
i++;
}
return cnt;
}
int main(){
cin >> n >> K;
for(int i = 0; i < n; i++)
cin >> a[i];
printf("%d\n", twoSum());
}🌰2、归并排序基础-两个有序序列合并为一个有序序列
晴问算法
把两个元素中更小的复制到新数组里，并更新指向该更小元素的指针一步，和更新新数组的指针一步。直到有一个指针到达序列尾即等于n/m, 则跳出循环，（只要有一个序列遍历完就跳出循环，因此进入循环的条件是两个序列都没遍历完！）最后把没遍历完的序列元素直接复制到新数组里。
#include <iostream>
using namespace std;
const int MAXN = 100000;
int a[MAXN], b[MAXN], merged[2*MAXN];
int n, m;
void Merge(){
int i = 0, j = 0, x = 0;
while(i < n && j < m){
if(a[i] > b[j]){
merged[x++] = b[j++];
}
else{
merged[x++] = a[i++];
}
}
while(i < n)
merged[x++] = a[i];
while(j < m)
merged[x++] = b[j];
}
int main(){
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> a[i];
for(int j = 0; j < m; j++)
cin >> b[j];
Merge();
for(int i = 0; i < n+m ; i++)
printf(i == n+m -1 ? "%d\n" : "%d ", merged[i]);
}🌰3、2路归并排序
晴问算法
2路归并排序的手写逻辑是：将序列里的元素两个两个分组，组内单独排序，再把排完序的分组当作一个整体，再次两个两个分组，组内再单独排序……依次类推。
而代码逻辑-分治思想与手写逻辑正好相反，它是自顶向下思考：把序列对半分成两个子序列，分别对两个子序列进行归并排序，再将两个有序子序列合并为有序序列-->上一题，所以可在归并排序函数里写一个辅助函数以合并两个有序序列。
把序列对半分：可以用int start, mid, end三个索引来标识左右两个子序列，【start . mid]是左子序列，[mid + 1, end]是右子序列。
做法1-分治做法（递归）
额外用一个临时数组来存储合并后的序列，方便辅助函数。
#include <iostream>
using namespace std;
const int MAXN = 1000;
int a[MAXN], merged[MAXN], n;
//将升序区间[start, mid],[mid + 1, end]合并为升序区间【L1， R2】：
void mergeTwo(int l1, int l2, int r1, int r2){
int i = l1, j = r1, index = 0;
int merged[MAXN];
//只有有一个序列遍历完就结束循环，因此进入循环的条件是两个序列都没遍历完！
while(i <= l2 && j <= r2){
if(a[i] < a[j])
merged[index ++] = a[i ++];
else
merged[index ++] = a[j ++];
}
while(i <= l2)
merged[index ++] = a[i++];
while(j <= r2)
merged[index ++] = a[j ++];
//将临时数组赋值回数组a:
for(i = 0; i < index; i++)
a[i + l1] = merged[i];
return ;
}
//对区间[start, end]进行归并排序：
void mergeSort(int start, int end){
if(start >= end)
return ;//or if( start < end ){ }
int mid = (start + end) / 2;
mergeSort(start, mid);//对左子区间归并排序
mergeSort(mid + 1, end);//对右子区间归并排序
mergeTwo(start, mid, mid+1, end);//合并归并排序好后的左右子区间
return ;
}
int main(){
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
mergeSort(0, n-1);
for(int i = 0; i < n; i++)
printf(i == n-1 ? "%d\n" : "%d ", a[i]);
}做法2-递推做法
与手写逻辑一样从底往上思考：先两个两个元素分组得到[n/2]个组（往上取整），然后组内单独排序，因为一个元素也可以视作一个有序序列，因此，此时对组内单独排序也就是：将两个有序序列合并为一个有序序列的问题了。再继续对已排好序的组两个两个分组得到[n/4]个组，此时一个组内，也包含了两个有序序列（组），因此再次合并两个有序序列。。。
我们可以观察到，每个分组里的元素个数上限一定是2的次方，比如2 8 5 1 3， 第一次分组每组的元素个数是2，2，1个，第二次分组每组的元素个数是4，1个（一个元素也可以视作一个有序序列）
且后一次分组里组内元素个数上限是前一次分组的2倍（因为合并了前一次分组），因此我们可以将循环步长step初始化为2，也就是说此次循环里每组的元素个数上限是step,将前step/2个元素的有序序列作为左子序列，如果右子序列存在元素，则合并；
更新step*2， 直到step / 2 >= n说明整个序列都作为左子序列了也即不需要在合并了，2路归并排序完成。
注意鲁棒性：
void mergeSort(int n){
//step表示此次分组的元素个数上限，step/2是左子序列的元素个数
for(int step = 2; step / 2 < n ; step *= 2){
//对每组[i, end]内单独合并左右两个有序子序列
for(int i = 0; i < n; i += step){
int mid = i + step / 2 -1;
//对于分组[3,]其右子序列没有元素，所以需判断右子序列是否存在元素，存在则合并：
if(mid+1 < n){
/*当对最后一组单独排序时，其右子序列的元素个数可能不满step/2，此时无法通过i+step-1定位右子序列的尾，
但是显然其尾元素是a[n-1]。因此只需做一个min选择 */
int end = min(i + step -1, n-1);
mergeTwo(i, mid, mid+1, end);
}
}
}
return ;
}