《算法笔记》总结No.8——双指针

去年发表过较简单的双指针案例，建议先行阅读~

C++实现双指针算法_c++ 双指针排序-CSDN博客文章浏览阅读154次。本贴介绍双指针的入门典例~_c++ 双指针排序https://jslhyh32.blog.csdn.net/article/details/129829790

---

 一.定义

相比说双指针是一种算法，他更倾向是一种编程技巧，话不多说直接看一个引例：

1.正整数和

如下，给定递增序列【1,3,5,7,9】，寻找到两个相加为16的元素。如果使用暴力的思想，相当于是一个双层循环：外层下标i对应的A[i]和内层下标为j的A[j]之和为16，则算一个合法的答案。

然而双层循环的复杂度为N方，当N特别大时，这显然是无法接受的。

但是仔细想一想不难发现——其实在这个暴力过程中出现了很多无用功：

• 当A[i]+A[j]＞16时，由于序列是递增的，所以A[i]+A[j+1]是必定大于16的，因此后面的查找是多余的
• 当A[i]+A[j]＞16时，还是由于递增的性质，显然也没必要比较A[i+1]+A[j]的值~

        不难发现，上面两种导致多余查找的原因在于，i和j的枚举是相互牵制的，因此要想到一种可以同时考虑i和j的算法——就有了接下来双指针的思想~ 

---

令下标i的值为0，而j的值为数组的长度n-1，然后根据 A[i]+A[j]和目标值M的大小关系进行3种不同的选择，直到j>i为止：

• 如果A[i]+A[j]=M：说明找到了一种方案，此时无论是A[i+1]+A[j]>M还是A[i]+A[j-1]<M均成立，但是A[i+1]+A[j-1]与M的关系却未知，因此要i+1且j-1
• 如果A[i]+A[j]>M：此时A[i+1]+A[j]>M必然成立，因此只能移动j，j=j-1
• 如果A[i]+A[j]<M：此时A[i]+A[j-1]<M必然成立，因此只能移动i，i=i-1

代码如下：

#include<iostream>
#include <vector>
#include <algorithm> 
using namespace std;
 
struct item{
	int i=0,j=0;
};
 
int  count(vector<int> V,vector<item>& I,int x)
{
	int ans=0;
	int i=0,j=V.size()-1;
	while(i<j)
	{
		if(V[i]+V[j]==x)
		{
			ans++;
			item temp;
			temp.i=i;
			temp.j=j;
			I.push_back(temp);
			i++;
			j--; 
		}
		else if(V[i]+V[j]>x)
			j--;
		else if(V[i]+V[j]<x)
			i++;
	}
	return ans;
}
 
int main(){
	int num=0;
	cout<<"请输入数组个数："<<endl;
	cin>>num;
	cout<<"请依次输入元素："<<endl;
	vector<int> V;
	vector<item> I;
	for(int i=1;i<=num;i++)
	{
		int temp=0;
		cin>>temp;
		V.push_back(temp);
	}
	sort(V.begin(),V.end());
	int x=0;
	cout<<"请输入待查询值："<<endl;
	cin>>x;
	int ans=count(V,I,x);
	cout<<"符合要求的答案有"<<ans<<"个："<<endl;
	
	for(int a=0;a<=I.size()-1;a++)
		cout<<I[a].i<<" "<<I[a].j<<endl;
}

别树一帜的写法，大家自行品味~

返回的值是下标~

此外一个新手很容易晕的小细节：

int  count(vector<int> V,vector<item>& I,int x)

第二个数组I是引用传递！因为要用到返回的结果，而返回值只是一个int，为了不让结果为空，一定要引用传递！！！

2.序列合并

存在两个递增序列A和B，请把他们按序合并到新的数组C中~

这个比较简单，还是使用双指针，按需扫描A和B即可，用每次扫出来的A[i]和B[j]做比较，这样排进C中的数据一定就是有序的~

代码如下：

#include<iostream>
#include <vector>
#include <algorithm> 
using namespace std;
 
void count(vector<int> A,vector<int> B,int x,int y)
{
	int i=0,j=0;
	while(i<x&&j<y) //当有某一个序列遍历完之后结束 
	{
		if(A[i]<=B[j]){
			cout<<A[i]<<endl;
			i++;
		}
		else{
			cout<<B[j]<<endl;
			j++;
		} 
	}
	//将未遍历完的那一个按序输出~ 
	while(i<x)
	{
		cout<<A[i]<<endl;
		i++;
	}
	while(j<y)
	{
		cout<<B[j]<<endl;
		j++;
	} 
}
 
int main(){
	int num1=0,num2=0;
	vector<int> A;
	vector<int> B;
	
	cout<<"请输入A数组个数："<<endl;
	cin>>num1;
	cout<<"请依次输入元素："<<endl;
	for(int i=1;i<=num1;i++)
	{
		int temp=0;
		cin>>temp; 
		A.push_back(temp);
	}
	sort(A.begin(),A.end());
	
	cout<<"请输入B数组个数："<<endl;
	cin>>num2;
	cout<<"请依次输入元素："<<endl;
	for(int i=1;i<=num2;i++)
	{
		int temp=0;
		cin>>temp;
		B.push_back(temp);
	}
	sort(B.begin(),B.end());	
 
	count(A,B,num1,num2);
 
}

几个点需要注意一下：

• 这里博主调用了sort函数，保证序列在调用函数的时候肯定是有序的，这个其实是多此一举的操作，为了方便可以乱序输入，实际上题干中给的数据已经是有序的
• 注意上面的while循环存在条件——两个数组都没有被遍历完，因此不难得到其否命题为有个已经被遍历完了。要注意，此处双指针的作用是比较两个数组最小元素的大小，如果有一个全部元素都比完了都没找到一个比另一个大的，则说明这个另一个中的剩余元素一定均大于之前遍历过的，因此直接按序输出即可~

测试一下，没什么bug：

（返回值类型也可以是vector<int> 数组，但是要注意负责存放排序后的值的那个数组一定要引用传参！ ） 

二.归并排序

这里介绍最简单的2-路归并排序：

假设现有数列【66,22,33,57,64,27,18】，排序的过程如下：

• 第一步，将所有元素两两划分，然后组内单独排序:【22,66】，【33,57】，【27,64】，【18】
• 第二步，合并相邻两个序列并排序：【22,33,57,66】、【18,27,64】
• 第三步，继续合并并排序【18,22,27,33,57,64,66】——得到答案

不难发现，核心在于如何将两个有序序列合并为一个有序序列——这一操作在上面已经实现~

此外，归并排序的复杂度为N*logN——对于限制N方的题目来说，这是非常好的排序手段！

1.递归实现

首先我们要对上面将有序序列合并的函数做出修改——使其可以在规定的区间内完成有序~

一步一步来，首先将上述修改成返回一个int型vector的函数，本质上没有发生任何改变：

vector<int> count(vector<int> A,vector<int> B)
{
	int i=0,j=0;
	int x=A.size(),y=B.size();
	vector<int> C;
	while(i<x&&j<y) //当有某一个序列遍历完之后结束 
	{
		if(A[i]<=B[j]){
			C.push_back(A[i]);
			i++;
		}
		else{
			C.push_back(B[j]);
			j++;
		} 
	}
	while(i<x)
	{
		C.push_back(A[i]);
		i++;
	}
	while(j<y)
	{
		C.push_back(B[j]);
		j++;
	} 
	return C;
}

然后需要注意，这时候参数要改了这里只是要实现：将某个数组中两个无序的区间合成为同一个有序的区间（数组），因此需要传入的参数应该是5个：目标数组，然后是4个区间端点！

合并函数如下：

vector<int> merge(vector<int> V,int x1,int y1,int x2,int y2)
{
	int i=x1-1,j=x2-1;//下标和位序相差一，这里符合惯性思维的赋值方式~ 
	vector<int> V1;
	while(i<=y1-1&&j<=y2-1) //当有某一个序列遍历完之后结束 
	{
		if(V[i]<=V[j]){
			V1.push_back(V[i]);
			i++;
		}
		else{
			V1.push_back(V[j]);
			j++;
		} 
	}
	while(i<=y1-1)
	{
		V1.push_back(V[i]);
		i++;
	}
	while(j<=y2-1)
	{
		V1.push_back(V[j]);
		j++;
	} 
	return V1;
}

在main函数测试一下效果：

int main(){
	int num1=0,num2=0;
	vector<int> A;
	vector<int> B;
	
	cout<<"请输入A数组个数："<<endl;
	cin>>num1;
	cout<<"请依次输入元素："<<endl;
	for(int i=1;i<=num1;i++)
	{
		int temp=0;
		cin>>temp; 
		A.push_back(temp);
	}
	int x1=0,x2=0,y1=0,y2=0;
	cout<<"请依次输入4个区间：";
	cin>>x1>>y1>>x2>>y2;
	vector<int> C;
	C=merge(A,x1,y1,x2,y2);
	for(int i=0;i<=C.size()-1;i++)
		cout<<C[i]<<" ";
 
}

想起来英语有一个单词叫做perfect~ 

        上面的区间就是我们高中学的数列中正常的位序——博主在代码中已经做了换算，大家直接输入位序即可！

        不过细心的同学可能会发现——如果我输入的A先入为主是有序的，还需要归并排序干嘛？这里实现的是两个区间，区间是人为给定好的，但是在归并排序里面，或者说这种2路归并排序，实际上参数值是某种固定的顺序。因此通过递归，将这个数组的区间不断细分，细分到只剩下一个元素的时候，实际上一下子就能比较出来，然后层层递进回来，上一层递归返回来的数组本身就是一个有序序列！

 因此来写我们的递归函数：

void mergeSort(vector<int> &V,int left,int right)
{
	if(left<right)
	{
		int mid =(left+right)/2;
		mergeSort(V,left,mid);
		mergeSort(V,mid+1,right);
		merge(V,left,mid,mid+1,right);
	}
} 

参数类型不同的时候代码可能会有不同的结果，大家自行尝试~ 

2.非递归实现 

非递归的大家自己看一下思路吧，博主能力有限，由于返回值类型的有效性，目前还没有较完美的实现~

三.快速排序 

依旧是一个复杂度为N*logN的排序算法。

---

这部分理论先放一下，直接上实现代码：

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
int part(int* r, int low, int hight)  //划分函数
{
	int i = low, j = hight, pivot = r[low]; //基准元素
	while (i < j)
	{
		while (i<j && r[j]>pivot) //从右向左开始找一个 小于等于 pivot的数值
		{
			j--;
		}
		if (i < j)
		{
			swap(r[i++], r[j]);  //r[i]和r[j]交换后 i 向右移动一位
		}
		while (i < j && r[i] <= pivot) //从左向右开始找一个 大于 pivot的数值
		{
			i++;
		}
		if (i < j)
		{
			swap(r[i], r[j--]);  //r[i]和r[j]交换后 i 向左移动一位
		}
	}
	return i;  //返回最终划分完成后基准元素所在的位置
}
void Quicksort(int* r, int low, int hight)
{
	int mid;
	if (low < hight)
	{
		mid = part(r, low, hight);  // 返回基准元素位置
		Quicksort(r, low, mid - 1); // 左区间递归快速排序
		Quicksort(r, mid+1, hight); // 右区间递归快速排序
	}
}
int main()
{
	int a[10001];
	int  N;
	cout << "请输入要排序的数据的个数： " << endl;
	cin >> N;
	cout << "请输入要排序的数据： " << endl;
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
	}
	cout << endl;
	Quicksort(a, 0, N - 1);
	cout << "排序后的序列为： " << endl;
	for (int i = 0; i < N; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}

---

写在最后：单说思想本身，个人感觉归并和快排已经是初学者除了DP最难的算法了，实现起来考虑到返回值类型什么的会更加困难一些。但考虑到比N方还要低的复杂度，这两种算法的性价比相当之高！这里先留个坑位，之后理论部分补充一些王道408的部分会更好一些~

对于基础的双指针算法，没什么理解起来的难度，需要注意的是等号的选取范围，以及while循环执行下去的条件，不同题目可能不尽相同。