《算法筆記》4.6小節(jié)——算法初步->two pointers

@[TOC]

Contest100000583 - 《算法筆記》4.6小節(jié)——算法初步->two pointers

two pointers理論與例題

4.6.1 什么是two pointers

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

即數(shù)列遞增有序：
比較a[i]+a[j]與M的值，
若等于，則i+1,j-1遞歸查詢；
若大于，則j-1遞歸查詢；
若小于，則i+1遞歸查詢。


在這里插入圖片描述

序列合并問題

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

4.6.2 歸并排序

在這里插入圖片描述

在這里插入圖片描述

遞歸實現(xiàn)

//4.6.2歸并排序

//###############################遞歸實現(xiàn)############# 
const int maxn = 100;
//將數(shù)組A的{L1,R1}與{L2,R2}區(qū)間合并為有序區(qū)間（此處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臨時存放合并后的數(shù)組，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];//將合并后的序列賦值回數(shù)組A 
    }
}
//將array數(shù)組當前區(qū)間[left,right]進行歸并排序
void mergeSort(int A[],int left,int right)
{
    if(left < right)
    {
        int mid = (left+right)/2;
        mergeSort(A,left,right);//遞歸歸并左子區(qū)間 
        mergeSort(A,mid+1,right);//遞歸歸并右子區(qū)間 
        merge(A,left,mid,mid+1,right);//合并左右區(qū)間  
    }   
}

非遞歸實現(xiàn)

在這里插入圖片描述
//********************非遞歸實現(xiàn)############# 有些疑惑QWQ
void mergeSort(int A[])
{
    //step為數(shù)組內(nèi)元素個數(shù)，step/2為左區(qū)間元素個數(shù)，注意等號可以不取
    for(int step = 2;step/2<=n;step*=2)
    {//每step個元素一組，組內(nèi)前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 快速排序

在這里插入圖片描述

思想與代碼

選取基準值，通過一趟排序使得整個序列被基準值分成小于基準值的部分和大于基準值的部分，然后分別在這兩部分內(nèi)部遞歸進行快速排序
一趟排序具體過程為：從后往前尋找比基準值小的元素與基準值交換位置；從前往后尋找比基準值大的元素與基準值交換位置，直至基準值到達最終位置


在這里插入圖片描述

在這里插入圖片描述
//4.6.3快速排序
//對區(qū)間[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);//對左子區(qū)間遞歸進行快排 
        quickSort(A,pos+1,right);//對右子區(qū)間遞歸進行快排 
        
    }
}

改進：隨機基準數(shù)

在這里插入圖片描述

在這里插入圖片描述
//4.6.3快速排序隨機數(shù)基準值 
//對區(qū)間[left,right]進行劃分
#include <cstdio>
#include <stdlib.h>
#include <time.h> 

int randPartition(int A[],int left,int right)
{
    //生成[left,right]內(nèi)的的隨機數(shù) 
    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);//對左子區(qū)間遞歸進行快排 
        quickSort(A,pos+1,right);//對右子區(qū)間遞歸進行快排 
        
    }
}

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;
//將數(shù)組A的{L1,R1}與{L2,R2}區(qū)間合并為有序區(qū)間（此處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臨時存放合并后的數(shù)組，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];//將合并后的序列賦值回數(shù)組A 
    }
}
//將array數(shù)組當前區(qū)間[left,right]進行歸并排序
void mergeSort(elemtype A[],int left,int right)
{
    if(left < right)
    {
        int mid = (left+right)/2;
        mergeSort(A,left,mid);//遞歸歸并左子區(qū)間 
        mergeSort(A,mid+1,right);//遞歸歸并右子區(qū)間 
        merge(A,left,mid,mid+1,right);//合并左右區(qū)間  
    }   
} 

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 基礎(chǔ)排序III：歸并排序

題目鏈接：http://codeup.cn/problem.php?cid=100000586&pid=1

//3105 Problem  B   基礎(chǔ)排序III：歸并排序
#include <iostream>
#include <cstdio>
using namespace std;
//typedef int elemtype;
//#define int int
const int maxn = 100005;
//將數(shù)組A的{L1,R1}與{L2,R2}區(qū)間合并為有序區(qū)間（此處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臨時存放合并后的數(shù)組，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];//將合并后的序列賦值回數(shù)組A 
    }
}
//將array數(shù)組當前區(qū)間[left,right]進行歸并排序
void mergeSort(int A[],int left,int right)
{
    if(left < right)
    {
        int mid = (left+right)/2;
        mergeSort(A,left,mid);//遞歸歸并左子區(qū)間 
        mergeSort(A,mid+1,right);//遞歸歸并右子區(qū)間 
        merge(A,left,mid,mid+1,right);//合并左右區(qū)間  
    }   
} 

int main()
{
    int num[maxn];
    int n;
    while(cin>>n)
    {
        while(n--)//輸入組數(shù) 
        {
            int m;
            cin>>m;//輸入每組的元素數(shù) 
            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;
//將數(shù)組A的{L1,R1}與{L2,R2}區(qū)間合并為有序區(qū)間（此處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臨時存放合并后的數(shù)組，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];//將合并后的序列賦值回數(shù)組A 
    }
}
//將array數(shù)組當前區(qū)間[left,right]進行歸并排序
void mergeSort(elemtype A[],int left,int right)
{
    if(left < right)
    {
        int mid = (left+right)/2;
        mergeSort(A,left,mid);//遞歸歸并左子區(qū)間 
        mergeSort(A,mid+1,right);//遞歸歸并右子區(qū)間 
        merge(A,left,mid,mid+1,right);//合并左右區(qū)間  
    }   
} 

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;
//將數(shù)組A的{L1,R1}與{L2,R2}區(qū)間合并為有序區(qū)間（此處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臨時存放合并后的數(shù)組，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];//將合并后的序列賦值回數(shù)組A 
    }
}
//將array數(shù)組當前區(qū)間[left,right]進行歸并排序
void mergeSort(elemtype A[],int left,int right)
{
    if(left < right)
    {
        int mid = (left+right)/2;
        mergeSort(A,left,mid);//遞歸歸并左子區(qū)間 
        mergeSort(A,mid+1,right);//遞歸歸并右子區(qū)間 
        merge(A,left,mid,mid+1,right);//合并左右區(qū)間  
    }   
} 

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;
}

總結(jié)下：

快排代碼很有用，延伸出的two pointers思想也賊妙

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容