@[TOC]
Contest100000583 - 《算法笔记》4.6小节——算法初步->two pointers
two pointers理论与例题
4.6.1 什么是two pointers
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
即数列递增有序：
比较a[i]+a[j]与M的值，
若等于，则i+1,j-1递归查询；
若大于，则j-1递归查询；
若小于，则i+1递归查询。
在这里插入图片描述
序列合并问题
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
4.6.2 归并排序
在这里插入图片描述
在这里插入图片描述
递归实现
//4.6.2归并排序
//###############################递归实现#############
const int maxn = 100;
//将数组A的{L1,R1}与{L2,R2}区间合并为有序区间（此处L2即为R1+1）
void merge(int A[],int L1,int R1,int L2,int R2)
{
int i=L1,j=L2;//i指向A[L1],j指向A[L2]
int temp[maxn],index=0;//temp临时存放合并后的数组，index为其下标
while(i <= R1 && j <= R2)
{
if(A[i] <= A[j])
{
temp[index++] = A[i++];//将A[i]加入序列temp
}
else
{
temp[index++] = A[j++];//将A[j]加入序列temp
}
}
while(i <= R1) temp[index++] = A[i++];//将[L1,R1]的剩余元素加入序列temp
while(j <= R2) temp[index++] = A[j++];//将[L2,R2]的剩余元素加入序列temp
for(i=0;i<index;i++)
{
A[L1+i] = temp[i];//将合并后的序列赋值回数组A
}
}
//将array数组当前区间[left,right]进行归并排序
void mergeSort(int A[],int left,int right)
{
if(left < right)
{
int mid = (left+right)/2;
mergeSort(A,left,right);//递归归并左子区间
mergeSort(A,mid+1,right);//递归归并右子区间
merge(A,left,mid,mid+1,right);//合并左右区间
}
}
非递归实现
在这里插入图片描述
//********************非递归实现############# 有些疑惑QWQ
void mergeSort(int A[])
{
//step为数组内元素个数，step/2为左区间元素个数，注意等号可以不取
for(int step = 2;step/2<=n;step*=2)
{//每step个元素一组，组内前step/2和后step/2个元素进行合并
for(int i=1;i<=n;i+=step)
{
int mid = i+step/2-1;
if(mid+1 <= n)
{
merge(A,i,mid,mid+1,min(i+step-1,n));
}
}
}
}
4.6.3 快速排序
在这里插入图片描述
思想与代码
选取基准值，通过一趟排序使得整个序列被基准值分成小于基准值的部分和大于基准值的部分，然后分别在这两部分内部递归进行快速排序
一趟排序具体过程为：从后往前寻找比基准值小的元素与基准值交换位置；从前往后寻找比基准值大的元素与基准值交换位置，直至基准值到达最终位置
在这里插入图片描述
在这里插入图片描述
//4.6.3快速排序
//对区间[left,right]进行划分
int Partition(int A[],int left,int right)
{
int temp = A[left];//将A[left]存放至临时变量temp
while(left<right)
{
while(left<right && A[right] > temp) right--;
A[left] = A[right];//从后往前扫描比基准值小的元素与基准值交换位置
while(left<right && A[left] <= temp) right--;
A[right] = A[left];//从前往后扫描比基准值大的元素与基准值交换位置
}
A[left] = temp;//把temp放到left与right相遇的地方
return left;//返回相遇的下标
}
//快速排序
void quickSort(int A[],int left,int right)
{
if(left<right)
{//将[left,right]按A[left]一分为二
int pos = Partition(A,left,mid);
quickSort(A,left,pos-1);//对左子区间递归进行快排
quickSort(A,pos+1,right);//对右子区间递归进行快排
}
}
改进：随机基准数
在这里插入图片描述
在这里插入图片描述
//4.6.3快速排序随机数基准值
//对区间[left,right]进行划分
#include <cstdio>
#include <stdlib.h>
#include <time.h>
int randPartition(int A[],int left,int right)
{
//生成[left,right]内的的随机数
int p = (round(1.0*rand()/RAND_MAX*(right-left))+left);
swap(A[p],A[left]);
int temp = A[left];//将A[left]存放至临时变量temp
while(left<right)
{
while(left<right && A[right] > temp) right--;
A[left] = A[right];//从后往前扫描比基准值小的元素与基准值交换位置
while(left<right && A[left] <= temp) right--;
A[right] = A[left];//从前往后扫描比基准值大的元素与基准值交换位置
}
A[left] = temp;//把temp放到left与right相遇的地方
return left;//返回相遇的下标
}
//快速排序
void quickSort(int A[],int left,int right)
{
if(left<right)
{//将[left,right]按A[left]一分为二
int pos = Partition(A,left,right);
quickSort(A,left,pos-1);//对左子区间递归进行快排
quickSort(A,pos+1,right);//对右子区间递归进行快排
}
}
Codeup习题练习
2934 Problem A 二路归并排序(mergesort)递归
题目链接：http://codeup.cn/problem.php?cid=100000586&pid=0
//2934 Problem A 二路归并排序(mergesort)递归法 [2*+]
//不知道为啥没通过
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long elemtype;
//#define int int
const elemtype maxn = 100005;
//将数组A的{L1,R1}与{L2,R2}区间合并为有序区间（此处L2即为R1+1）
void merge(elemtype A[],int L1,int R1,int L2,int R2)
{
int i=L1,j=L2;//i指向A[L1],j指向A[L2]
elemtype temp[maxn];
int index=0;//temp临时存放合并后的数组，index为其下标
while(i <= R1 && j <= R2)
{
if(A[i] <= A[j])
{
temp[index++] = A[i++];//将A[i]加入序列temp
}
else
{
temp[index++] = A[j++];//将A[j]加入序列temp
}
}
while(i <= R1) temp[index++] = A[i++];//将[L1,R1]的剩余元素加入序列temp
while(j <= R2) temp[index++] = A[j++];//将[L2,R2]的剩余元素加入序列temp
for(i=0;i<index;i++)
{
A[L1+i] = temp[i];//将合并后的序列赋值回数组A
}
}
//将array数组当前区间[left,right]进行归并排序
void mergeSort(elemtype A[],int left,int right)
{
if(left < right)
{
int mid = (left+right)/2;
mergeSort(A,left,mid);//递归归并左子区间
mergeSort(A,mid+1,right);//递归归并右子区间
merge(A,left,mid,mid+1,right);//合并左右区间
}
}
int main()
{
elemtype num[maxn];
elemtype n;
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>num[i];
}
mergeSort(num,0,n-1);
for(int i=0;i<n;i++)
cout<<num[i]<<endl;
}
return 0;
}
3105 Problem B 基础排序III：归并排序
题目链接：http://codeup.cn/problem.php?cid=100000586&pid=1
//3105 Problem B 基础排序III：归并排序
#include <iostream>
#include <cstdio>
using namespace std;
//typedef int elemtype;
//#define int int
const int maxn = 100005;
//将数组A的{L1,R1}与{L2,R2}区间合并为有序区间（此处L2即为R1+1）
void merge(int A[],int L1,int R1,int L2,int R2)
{
int i=L1,j=L2;//i指向A[L1],j指向A[L2]
int temp[maxn],index=0;//temp临时存放合并后的数组，index为其下标
while(i <= R1 && j <= R2)
{
if(A[i] <= A[j])
{
temp[index++] = A[i++];//将A[i]加入序列temp
}
else
{
temp[index++] = A[j++];//将A[j]加入序列temp
}
}
while(i <= R1) temp[index++] = A[i++];//将[L1,R1]的剩余元素加入序列temp
while(j <= R2) temp[index++] = A[j++];//将[L2,R2]的剩余元素加入序列temp
for(i=0;i<index;i++)
{
A[L1+i] = temp[i];//将合并后的序列赋值回数组A
}
}
//将array数组当前区间[left,right]进行归并排序
void mergeSort(int A[],int left,int right)
{
if(left < right)
{
int mid = (left+right)/2;
mergeSort(A,left,mid);//递归归并左子区间
mergeSort(A,mid+1,right);//递归归并右子区间
merge(A,left,mid,mid+1,right);//合并左右区间
}
}
int main()
{
int num[maxn];
int n;
while(cin>>n)
{
while(n--)//输入组数
{
int m;
cin>>m;//输入每组的元素数
for(int i=0;i<m;i++)
{
cin>>num[i];
}
mergeSort(num,0,m-1);
for(int i=0;i<m;i++)
cout<<num[i]<<endl;
}
}
return 0;
}
2843 Problem C 快速排序 qsort [2*]
题目链接：http://codeup.cn/problem.php?cid=100000586&pid=2
//2843 Problem C 快速排序 qsort [2*]
//不知道为啥没通过
#include <iostream>
#include <cstdio>
using namespace std;
typedef int elemtype;
//#define int int
const elemtype maxn = 100005;
//将数组A的{L1,R1}与{L2,R2}区间合并为有序区间（此处L2即为R1+1）
void merge(elemtype A[],int L1,int R1,int L2,int R2)
{
int i=L1,j=L2;//i指向A[L1],j指向A[L2]
elemtype temp[maxn];
int index=0;//temp临时存放合并后的数组，index为其下标
while(i <= R1 && j <= R2)
{
if(A[i] <= A[j])
{
temp[index++] = A[i++];//将A[i]加入序列temp
}
else
{
temp[index++] = A[j++];//将A[j]加入序列temp
}
}
while(i <= R1) temp[index++] = A[i++];//将[L1,R1]的剩余元素加入序列temp
while(j <= R2) temp[index++] = A[j++];//将[L2,R2]的剩余元素加入序列temp
for(i=0;i<index;i++)
{
A[L1+i] = temp[i];//将合并后的序列赋值回数组A
}
}
//将array数组当前区间[left,right]进行归并排序
void mergeSort(elemtype A[],int left,int right)
{
if(left < right)
{
int mid = (left+right)/2;
mergeSort(A,left,mid);//递归归并左子区间
mergeSort(A,mid+1,right);//递归归并右子区间
merge(A,left,mid,mid+1,right);//合并左右区间
}
}
int main()
{
elemtype num[maxn];
elemtype n;
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>num[i];
}
mergeSort(num,0,n-1);
for(int i=0;i<n;i++)
cout<<num[i]<<endl;
}
return 0;
}
2932 Problem D 二分递归快排（Qsort） [2*]
题目链接：http://codeup.cn/problem.php?cid=100000586&pid=3
//2932 Problem D 二分递归快排（Qsort） [2*]
#include <iostream>
#include <cstdio>
using namespace std;
typedef int elemtype;
//#define int int
const elemtype maxn = 100005;
//将数组A的{L1,R1}与{L2,R2}区间合并为有序区间（此处L2即为R1+1）
void merge(elemtype A[],int L1,int R1,int L2,int R2)
{
int i=L1,j=L2;//i指向A[L1],j指向A[L2]
elemtype temp[maxn];
int index=0;//temp临时存放合并后的数组，index为其下标
while(i <= R1 && j <= R2)
{
if(A[i] <= A[j])
{
temp[index++] = A[i++];//将A[i]加入序列temp
}
else
{
temp[index++] = A[j++];//将A[j]加入序列temp
}
}
while(i <= R1) temp[index++] = A[i++];//将[L1,R1]的剩余元素加入序列temp
while(j <= R2) temp[index++] = A[j++];//将[L2,R2]的剩余元素加入序列temp
for(i=0;i<index;i++)
{
A[L1+i] = temp[i];//将合并后的序列赋值回数组A
}
}
//将array数组当前区间[left,right]进行归并排序
void mergeSort(elemtype A[],int left,int right)
{
if(left < right)
{
int mid = (left+right)/2;
mergeSort(A,left,mid);//递归归并左子区间
mergeSort(A,mid+1,right);//递归归并右子区间
merge(A,left,mid,mid+1,right);//合并左右区间
}
}
int main()
{
elemtype num[maxn];
elemtype n;
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>num[i];
}
mergeSort(num,0,n-1);
for(int i=0;i<n;i++)
cout<<num[i]<<endl;
}
return 0;
}
总结下：
快排代码很有用，延伸出的two pointers思想也贼妙
网友评论