学习一些入门算法应该不会很难吧，哈哈(C++)

快排

假设q[n]是一个整数数组需要排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void quicksort(int q[],int l,int r)
{
    ​ if (l >= r) return;
    ​ int mid = q[l];
    ​ int i = l - 1, j = r + 1;
    ​ while (l < r)
    {
        ​ do { i++; }
        ​ while (q[i] < mid);
        ​ do { j++; }
        ​ while (q[j] > mid);
        ​ if (i < j) swap(q[i], q[j]);
    }
    ​ quicksort(q, l, j); //这时不能用i-1，因为最后不一定就是i>j也可能是i=j，就可能i-1会比l小
    ​ quicksort(q, j + 1, r); //
}

归并

​ 分两步：递归和合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void merge(int q[], int l, int r)
{
    if (l >= r)
        return;
    int mid = l + r >> 1;
    merge(q, l, mid);//一开始就要递归
    merge(q, mid + 1, r);
    for (int i = l; i <= r; i++)//把q数组l到r的内容复制到p
        p[i] = q[i];
    int i = l, j = mid + 1, x = l;
    while (i <= mid && j <= r)//进行合并，循环条件是两部分没有到端点
    {
        if (p[i] < p[j])//把的那个放入q中
            q[x++] = p[i++];
        else
            q[x++] = p[j++];
    }
    if (i <= mid)//如果一方没到终点则直接放到q后面
    {
        while (i <= mid)
            q[x++] = p[i++];
    }
    else
        while (j <= r)
            q[x++] = p[j++];
}

整数二分

1.从左往右逼近

解释：1 2 2 2 2 2 3，在这里面找2的话，二分肯定要取1到2，或者是2到3这个区间，但是不可能找到2到2这个区间，所以会失去一些数

1
2
3
4
5
6
7
8
9
10
11
12
13
int half(int q[], int l, int r, int x)
{ //找x
    int mid = l + r >> 1;
    while (l < r)
    {
        mid = l + r + 1 >> 1;
        if (q[mid] <= x)
            l = mid;
        else
            r = mid - 1;
    }
    cout << r;
}

2.从右往左逼近

1
2
3
4
5
6
7
8
9
10
11
12
13
int half(int q[], int l, int r, int x)
{ //找x
    int mid ;
    while (l < r)
    {
        mid = l + r  >> 1;
        if (q[mid] >=x)
            r = mid;
        else
            l = mid+1;
    }
    cout << l;
}

单源汇最短路

一般来说是某一个点到其他点的最短距离

多源汇最短路

一般来说是求任意两个点之间的最短距离

数学知识

欧拉函数

扩展欧几里得

`

1
2
3
4
5
6
7
8
9
10
int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y=y-a/b*x;
    return d;
}

`