算法笔记（一）基础算法

目录

快速排序

题目

归并排序

题目：

acwing 788. 逆序对的数量

二分

整数

浮点数

题目

acwing \800. 数组元素的目标和数组元素的目标和

前缀和

一维

二维

题目

差分

一维

二维

题目

位运算

二进制进行运算

解法一

解法二

快速排序

思想是分治，讲数据分为左右两个区间，最后进行递归处理；（注意数据边界问题）

序列中选择一个数x(l或r或中间)，两个指针i和j从左侧和右侧向中间移动，i遇到大于x时停，j遇到小于x时停，然后交换，直至相遇。相遇后递归。

例子：

#include
#include 
#include 
#include //包含swap库函数
using namespace std;
const int N = 1e6+10;//1000010
int q[N];
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    //do while 数据范围
    int i = l - 1, j = r + 1, x = q[(l+r)/2];
    while (i  x);
        if (i  
题目
 
 
归并排序
 
分治思想 先递归，在排序
 
先对序列进行递归，mid取中间值。在每一个merge过程中，i和j两个指针指向两个子序列开头，谁小谁进tmp数组。
 
 
例子：
 
 
#include 
using namespace std;
​
const int N = 100010;
int n;
int a[N];
int temp[N];
​
void merge_sort(int a[], int l, int r){
    //只剩一个元素的时候，已经有序，返回
    if(l >= r) return;
​
    //寻找数组中点下标
    int mid = (l+r)>>1;
    //递归给左半边排序
    merge_sort(a,l,mid);
    //递归给右半边排序
    merge_sort(a,mid+1,r);
    //以下是合并排序好的两个数组
​
    //k：遍历合并后的数组的下标
    int k = 0;
    //i:左半边数组的下标，j:右半边数组的下标
    int i = l, j = mid + 1;
    //左右半边都没遍历完
    while(i =r) return;
    int mid=(l+r)/2;
    quick(q,l,mid);
    quick(q,mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i eps)//相差两位
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}
 
题目
 
acwing 789. 数的范围
 
acwing 0. 数组元素的目标和数组元素的目标和
 
//二分做法
#include 
#include 
#include 
const int N = 1e5+10;
long int a[N],b[N];
using namespace std;
int search(long int q[],int l, int r,int x)
{
    while (l > 1;
        if (q[mid]>=x) r = mid;
        else l = mid + 1;
    }
    if(q[l]==x){
        return l;
    }
    return -1; 
}
int main()
{
     int n,m,s;
    scanf("%d%d%d", &n, &m,&s);
    for (int i = 0; i > a[i];
    }
    for (int i = 0; i > b[i];
    }
    for (int i = 0; i 

本网站所收集的部分公开资料来源于AI生成和互联网，转载的目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。