算法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--;elsei++;}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 ;
}