基础算法 | Borwin的小窝

快排

时间复杂度为O(nlogn)

算法概述：快排排序算法的核心是分治算法，往细一点讲就是：指定一个中间值，对序列进行划分，左部分全部小于该中间值，右部分全部大于中间值

之后再对所划分成的两个部分再进行划分（递归处理），最后达成排序的效果。

void quick_sort(int a[],int l,int r)
{
    if(l>=r) return;

    int mid=a[l+r>>1],le=l-1,re=r+1;
    
    while(le<re)
    {
        do le++; while(a[le]<mid);
        do ri--; while(a[ri]>mid);
        if(le<ri)swap(a[le],a[ri]);
    }
    
    quick_sort(l,re);
    quick_sort(re+1,r);
}

可能会有人对以下递归中的参数有所疑问

quick_sort(l,re); quick_sort(re+1,r);

re指向的是从右到左的第一个小于mid的数，相当于要对从l到re进行排序，从re+1到r进行排序,这样解释是不是容易懂一些了呢？

归并排序

时间复杂度:O(nlogn)

分治的思想，及将序列分成两个部分，将这两个部分分别排序,之后合并为一个序列。

void merge_sort(int a[],l,r)
{
    if(l>=r)return;//递归结束条件
    
    int mid=l+r>>1,le=l,ri=mid+1;
    
    merge_sort(a,l,mid);merge_sort(a,mid+1,r);//分别排序
    
    vector<int>c;//用于暂存合并后的排序好的数组
    
    while(le<ri)//合并数组
        if(a[le]<=a[ri])c.push_back(a[le++]);
        else c.push_back(a[ri++]);
    
    //可能会出现一边没有填入vector完的情况
    while(le<=mid)c.push_back(a[le++]);
    while(ri<=r)c.push_back(a[ri++]);
    
    //将暂存的数据填入原来的数组中
    for(int i=l,k=0;i<=r;i++,k++)a[i]=c[k];
}

其实在算法题中直接调用sort函数就行了(在数组比较短的时候是插入排序，数组比较长的时候是快排)，了解以上两种排序算法其实是加深对分治的理解，除了这几种排序算法外还有冒泡排序、选择排序等算法。

排序算法能够做到的最好的时间复杂度就是O(nlogn)了。

二分

此模板不用考虑mid+1或mid-1的情况,比Y总的模板好用qwq

int l=-1,r=n;//n为数组长度,数组从0开始存储时这样初始化
while(l+1!=r)
{
    if(check())l=mid;
    else r=mid;
}//最后根据实际情况选取l或者r作为结果

下面详细讲一下这串代码:

为什么L的初始值为-1，R的初始值为N?

这样赋值可以保证数组不会越界

为什么循环结束的条件是while(L+1!=R)?

之前学过二分的小伙伴可能会发现，之前学的二分，他循环结束的条件是while(L<R)

而这边给出的循环条件是while(L+1!=R) 其实，就是当L和R相邻的时候，循环就结束，而原本的while(L<R)

是当两区间重合以后，循环才结束，所以之前我们需要判断对mid进行加一或者减一的操作，而且因为区间重合的问题，最后返回的L、R还要再进行判断，而这边的这个二分，因为区间反回的是不重合的两区间，只有L=mid和R=mid这两种情况，最后根据需要返回L或者R；

为什么不会陷入死循环?

对于比较奇葩的情况，比如数组大小为1或者2

比如int a[1],b[2];

由于我们是while(L+1!=R)结束循环，也就是当L和R相邻的时候结束条件

对于a[1],他的下标为0 此时L=-1，R=n也就是1

对于b[2],他的下标为0,1 此时L=-1，R=n也就是2

所以无论何种情况，初始的L+1始终小于R，历经循环后最终L和R相邻，不会出现一开始L就和R重合等情况导致出现while(L+1!=R)循环不能结束的情况

前缀和

前缀和算法适用于要经常取出数组中某一段的和的时候，能够将O(n)的取和操作优化为O(1)
就像它的名字一样，前缀和就是从数组开头一直到某个序号处的所有元素的和。

//假如有数组a[n+1],元素个数为n,从a[1]开始记录数据
int head_sum[n];
head_sum[0]=0;
for(int i=1;i<=n;i++)head_sum[i]=head_sum[i-1]+a[i];

差分

差分数组可以说是取前缀的逆运算，差分数组的前缀和数组为原数组，差分用于对某一段连续的区间进行加减操作

1
2
3

int sub[n];
sub[0]=0;
for(int i=1;i<=n;i++)sub[i]=a[i]-a[i-1];

双指针

双指针在多数情况下为左右指针与快慢指针的应用，当然也有一些情况需要灵活运用，下面举两个具体的例子，分别是左右指针与快慢指针的。

左右指针

题目:输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

显然，这题用暴力做法的时间复杂度为O(n^2),但是如果我们用双指针就大不一样了(O(n))，见如下代码：

//假定一定存在这样的一对数的和为s,假设我们已知数组的长度为n,且从1开始存储数据
int l=1,r=n,res=0;
while(l<r)
{
    while(a[l]+a[r]>s && l<r)r--;
    if(a[l]+a[r]==s)
    {
        printf("%d %d",a[l],a[r]);
        break;
    }
    l++;
}