基础算法

1-1 排序

算法分类
十种常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

时间复杂度图：

1-1-1 快速排序

思路：

1. 确定分界点
   给定一个x，使其数组q分成左右两段
2. 调整区间，使其排序
   令x左面的数全部小于等于x，令x右边的数全部大于等于x
3. 递归:不断进行排序
   使q[n]分成n个这样的段落，重复以上的步骤，得以排序

//快排升序模板
void quick_sort(int l,int r)
{
    if(l>=r) return;//当数组q被递归到数组长度为1时停止
    
    int i=l-1,j=r+1;//设置两个指针，令其移动
    int x=q[l+r>>1];//x为分界点
    while(i<j)//排序
    {
        while(q[++i]<x);//do i++; while(q[i]<x);
        while(q[--j]>x);//do j--; while(q[j)>x);
        if(i<j) swap(q[i],q[j]);//当x的左右两边停止说明不满足左边小于x和右边大于x，此时，对q[i]和q[j]互换，while循环可继续进行下去
    }
    //while循环结束，则满足x左边小于x，x右边大于x这一条件

      //递归操作
      //不断进行递归，当数组递归到数组长度为3时，确定这一数组存在单调性
    quick_sort(l,j);
    quick_sort(j+1,r);
    //递归完成后，数组排序完成
}

注意：在主函数调用quick_sort函数时，应为

quick_sort(0,n-1);

时间复杂度为：O(nlogn)

1-1-2 归并排序

思路：分而治之

1. 确定分界点：取中间值mid=(l+r)/2
2. 递归 ：排序两边
3. 归并：合二为一，比较两段中更小值把其放入原数组；若最后有一个数组剩下数值，则将其全部放入原数组中

int q[N],tmp[N];
void merge_sort(int l,int r)
{
    if(l>=r) return;//退出递归
    
    int mid=(l+r)>>1;//确定分界点，分成两段
    int i=l,j=mid+1,k=0;
    
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    
    while(i<=mid&&j<=r)//比较左右两段
        if(q[i]>=q[j]) tmp[k++]=q[j++];//如果两段同时出现相等的数，一般将第一个段的数放入tmp中，因为归并排序是稳定的
        else tmp[k++]=q[i++];
        
    while(i<=mid) tmp[k++]=q[i++];//j段用完，i段全部放入
    while(j<=r) tmp[k++]=q[j++];//i段用完，j段全部放入
    
    for(int i=l,j=0;i<=r;i++) q[i]=tmp[j++];//将排列好的数据放入原数组
}

时间复杂度：O(nlogn)
比快排更稳定

1-2二分查找

• 二分查找也称折半查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

1-2-1整数二分

思路：

1. 寻找可以判断确定边界点的check函数
2. 给定mid的值
3. 用check函数进行判断，确定此刻mid值应该属于左边界还是右边界

void check_1(```)//右边满足性质

void check_2(```)//左边满足性质

int bsearch_1(int l,int r)//取左边界
{
    while(l<r)
    {
        int mid=l+r>>1;//mid在右半边
        if(check_1) r=mid;
        else l=mid+1;
    }
    return l;
}

int bsearch_2(int l,int r)//取右边界
{
    while(l<r)
    {
        int mid=l+r+1>>1;//mid在左半边
        if(check_2) l=mid;
        else r=mid-1
    }
    return l;
}

1-2-2浮点数二分

思路：同整数二分

//代码模板
    while(r-l>=1e-8)//这里最好是比题目中给定数据范围大e2，这样更精确
    {
        mid=(l+r)/2;
        if(check) l=mid;
        else r=mid;
    }

1-3高精度

• 高精度算法用于处理计算机中大计算数字的方法，由于在计算机中一个变量的存储长度是有限的，但是我们很容易在算法竞赛中计算，几百亿甚至千亿的大数字，此时就需要使用高精度算法，我们将大数字拆开，逐个放入数组中，对其进行计算。

1-3-1高精度加法

思想：我觉得这个方法很像计算机组成原理中的加法器

1. 高精度加法的思想类似于小学的计算方法，从个位开始一位一位的进行计算，把其化简为简单的一位数相加
2. 设置一个标记t，令他作为两数相加的合，储存到结果中

vector<int>add(vector<int>&A,vector<int>&B)
{
    vector<int>C;//定义一个数组c，用来存储两个数相加的结果
    
    int t=0;//t作为标记
    for(int i=0;i<A.size()||i<B.size();i++)//因为数组A和数组B的长度可能不一样，所以当其中一个数组走完时另一个数组直接存放到结果C中便可
    {
        if(i<A.size())t+=A[i];//i小于A的长度时，则令A存放到t中
        if(i<B.size())t+=B[i];//同理
        C.push_back(t%10);//将两数相加的个位结果放入C中
        t/=10;//若t>10则说明产生进位，让t等于进位，参与到下一次结果的运算
    }
    
    if(t)C.push_back(t);//当计算到最后一位数时，t可能产生进位，由于是两数相加，所以直接把t放进去即可
    return C;
}

1-3-2高精度减法

思想：

1. 高精度减法的思想类似于小学的减法，同样是从个位开始进行计算，把其化简为简单的一位数相减
2. 同样设置一个标记t，用来存储两数相减结果

vector <int> sub (vector<int> A,vector<int> B)
{
    vector <int> C;
    
    int t=0;
    
    for(int i=0;i<A.size();i++)
    {
        t+=A[i];
        if(i<B.size()) t-=B[i];
        
        C.push_back((t+10)%10);
        
        if(t<0) t=-1;
        else t=0;
    }
    
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}

注意：

1. 在存入A,B时应倒序存入，在输出C的时候也应倒序输出
2. 因为是减法，所以还存在比较A,B长度的问题，以及符号的问题

1-3高精度

• 高精度算法用于处理计算机中大计算数字的方法，由于在计算机中一个变量的存储长度是有限的，但是我们很容易在算法竞赛中计算，几百亿甚至千亿的大数字，此时就需要使用高精度算法，我们将大数字拆开，逐个放入数组中，对其进行计算。

1-3-1高精度加法

思想：我觉得这个方法很像计算机组成原理中的加法器

1. 高精度加法的思想类似于小学的计算方法，从个位开始一位一位的进行计算，把其化简为简单的一位数相加
2. 设置一个标记t，令他作为两数相加的合，储存到结果中

vector<int>add(vector<int>&A,vector<int>&B)
{
    vector<int>C;//定义一个数组c，用来存储两个数相加的结果
    
    int t=0;//t作为标记
    for(int i=0;i<A.size()||i<B.size();i++)//因为数组A和数组B的长度可能不一样，所以当其中一个数组走完时另一个数组直接存放到结果C中便可
    {
        if(i<A.size())t+=A[i];//i小于A的长度时，则令A存放到t中
        if(i<B.size())t+=B[i];//同理
        C.push_back(t%10);//将两数相加的个位结果放入C中
        t/=10;//若t>10则说明产生进位，让t等于进位，参与到下一次结果的运算
    }
    
    if(t)C.push_back(t);//当计算到最后一位数时，t可能产生进位，由于是两数相加，所以直接把t放进去即可
    return C;
}

1-3-2高精度减法

思想：

1. 高精度减法的思想类似于小学的减法，同样是从个位开始进行计算，把其化简为简单的一位数相减
2. 同样设置一个标记t，用来存储两数相减结果

vector <int> sub (vector<int> A,vector<int> B)
{
    vector <int> C;
    
    int t=0;
    
    for(int i=0;i<A.size();i++)
    {
        t+=A[i];
        if(i<B.size()) t-=B[i];
        
        C.push_back((t+10)%10);
        
        if(t<0) t=-1;
        else t=0;
    }
    
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}

注意：

1. 在存入A,B时应倒序存入，在输出C的时候也应倒序输出
2. 因为是减法，所以还存在比较A,B长度的问题，以及符号的问题

1-3-3高精度乘法（大数×小数）

思想：
1.同样以小学乘法模拟，不过与加法和减法不同的是，此处的b为小数，把A简化为一位数去乘以b
2.同样设置一个变量t用于存储一位数乘以b的结果

vector<int> mul(vector<int>&A,int b)
{
    vector<int> C;
    int t=0;
    for(int i=0;i<A.size()||t;i++)
    {
        if(i<A.size())t+=A[i]*b;
        C.push_back(t%10);
        t/=10;
    }
    
    while(C.size()>1&&C.back()==0)C.pop_back();
    return C;
}

部分关于排序的描述来源于
链接: 十大经典排序算法（动图演示）