1 排序算法

  • 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
img

1.1 冒泡排序

img 
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
27
28
29
30
31
32
33
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define N 10
class myPrint {
public:
	void operator()(int& val) {
		cout << val << " ";
	}
};
int main(){
	vector<int> vec;
	srand((unsigned int)time(NULL));
	for (int i = 0; i < N; i++) {
		vec.push_back(rand());
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N - i - 1; j++) {
			if (vec[j] < vec[j + 1]){
				int temp = vec[j];
				vec[j] = vec[j + 1];
				vec[j + 1] = temp;
			}
		}
	}

	for_each(vec.begin(), vec.end(), myPrint());
	cout << endl;

	return 0;
}

1.2 选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

以此类推，直到所有元素均排序完毕。

img 
1
2
3
4
5
6
7
8
9
10
11
for (int i = 0; i < N; i++) {
	int flag = i;
	for (int j = i; j < N; j++) {
		if (vec[j] > vec[flag]) {
			flag = j;
		}
	}
	int temp = vec[flag];
	vec[flag] = vec[i];
	vec[i] = temp;
}

1.3 插入排序

  • 从第一个元素开始，该元素可以认为已经被排序；
  • 在已经排序的元素序列中从后向前扫描；
  • 如果该元素（已排序）大于新元素，将该元素移到下一位置；
img 
1
2
3
4
5
6
7
8
9
for (int i = 1; i < N; i++) {
	int current_i = i;
	int count = vec[i];
	while (current_i > 0 && count < vec[current_i - 1]) {
		vec[current_i] = vec[current_i - 1];
		current_i--;
	}
	vec[current_i] = count;
}

1.4 希尔排序(Shell Sort)

直接插入排序算法的一种更高效的改进版本

把无序数组通过分组，分组之间比较进行移动，最后形成一个有序数组

在这里插入图片描述 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int gap = N / 2; gap > 0; gap /= 2) {//为1的时候就不需要继续排序了
	for (int i = 0; i < gap; i++) {
		//以下可以看作插入排序的实现
		for (int j = i; j < N; j += gap) {
			int count = vec[j];
			int current_j = j;
			while (current_j - gap >= 0 && count > vec[current_j-gap]) {
				vec[current_j] = vec[current_j - gap];
				current_j -= gap;
			}
			vec[current_j] = count;
		}
	}
}

1.5 归并排序

将未排序的列表划分为n个子列表，每个子列表包含一个元素

img
img
img 
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void merge(vector<int> &arr, int* tmp, int left, int right) {
	if (left >= right)return;
    //分
	int mid = (left + right) / 2;
	merge(arr, tmp, left, mid);
	merge(arr, tmp, mid + 1, right);
	//治
    int begin_left = left;
	int end_left = mid;
	int begin_right = mid + 1;
	int end_right = right;
	int i = begin_left;
	while (begin_left <= end_left && begin_right <= end_right) {
		if (arr[begin_left] > arr[begin_right]) {
			tmp[i++] = arr[begin_left++];
		}
		else {
			tmp[i++] = arr[begin_right++];
		}
	}
	while (begin_left <= end_left) {
		tmp[i++] = arr[begin_left++];
	}

	while (begin_right <= end_right) {
		tmp[i++] = arr[begin_right++];
	}
	//数据拷贝
	for (int j = left; j <= right; j++) {
		arr[j] = tmp[j];
	}
}

void merge_sort(vector<int> &arr) {
	int* tmp = new int[arr.size()];
	if (tmp == NULL) {
		perror("内存分配错误，指针指向NULL");
		exit(-1);
	}
	merge(arr, tmp, 0, arr.size() - 1);
	delete[] tmp;
}

1.6 快速排序（Quick Sort）

注意：快排必须先从右边开始扫描，不然要出错。

why？https://www.cnblogs.com/cai170221/p/13558104.html

1.6.1 挖坑法

20210515183213169.gif#pic_center 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void QuickSort(vector<int> &arr, int left, int right)
{
	if (left >= right)return;
	int key = arr[left];
	int begin = left;
	int end = right;
	int flag = left;
	while (begin < end) {
		while (begin < end && arr[end] >= key) {
			end--;
		}
		arr[flag] = arr[end];
		flag = end;
		while (begin < end && arr[begin] <= key) {
			begin++;
		}
		arr[flag] = arr[begin];
		flag = begin;
	}
	arr[flag] = key;
	QuickSort(arr, left, flag - 1);
	QuickSort(arr, flag + 1, right);
}

1.6.2 霍尔法

请添加图片描述 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void QuickSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    
    int begin = left;
    int end = right;
    int key = arr[left];
    
    while (begin < end) {

        while (begin < end && arr[end] >= key) {
            end--;
        }
		while (begin < end && arr[begin] <= key) {
			begin++;
		}
        swap(arr[begin], arr[end]);
    }
    swap(arr[left], arr[begin]);
    QuickSort01(arr, left, begin - 1);
    QuickSort01(arr, begin + 1, right);
}

2 快速幂与快速乘

\[ 计算3^5\\ (5)_H=(101)_2\\ 3^5 = 3^4*3^1 \]

1
2
3
4
5
6
7
8
9
10
int qpow(int a, int n){
    int ans = 1;
    while(n){
        if(n&1)        //如果n的当前末位为1
            ans *= a;  //ans乘上当前的a
        a *= a;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;
}

取模运算规则：

1
2
3
4
(a + b) % p = (a % p + b % p)%p
(a - b) % p = (a % p - b % p)%p
(a * b) % p = ((a % p) * (b % p))%p
(a ^ b) % p = ((a % p)^b) %p

\[ 计算3^{15}\%7 \]

1
2
3
4
5
6
7
8
9
int qpow(int a, int n){
	int ans = 1;
    while(n){
        if(n&1) ans = (ans * a)%7;
        a = (a * a)%7;
        n>>=1;
    }
    return ans;
}

同理，快速乘有类似的算法

1
2
3
4
5
6
7
8
9
10
11
int qcg(int a, int b, int p)
{
	int res = 0;
	while (b)
	{
		if (b & 1)res = ((LL)res + a) % p;
		a = ((LL)a + a) % p;
		b >>= 1;
	}
	return res;
}

3 KMP字符串匹配

最长相等前后缀：

1
2
3
4
5
6
7
8
9
例1：aba
前缀：a，ab
后缀：a, ba
最长相等前后缀：a，最长相等前后缀长度是1

例2：aaaa
前缀：a，aa, aaa
后缀：a , aa, aaa
最长相等前后缀：aaa，最长相等前后缀长度是3

next数组：

数组每一位记录匹配串到当前为止的最长相等前后缀长度

1
2
匹配串：a b a b c a b a b a
	   0 0 1 2 0 1 2 3 4 3
1
2
3
4
5
6
7
8
9
10
11
12
void get_next(const string str, int* next) {
    int j = 0;
    next[0] = 0;
    for (int i = 1; i < str.size(); i++) {
        //前后缀不相同怎么处理
        while (j > 0 && str[i] != str[j]) j = next[j - 1];
        //前后缀相同怎么处理
        if (str[i] == str[j]) j++;     
        
        next[i] = j;
    }
}

KMP

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
27
28
29
30
#include <iostream>
using namespace std;
void get_next(const string str, int* next) {
    int j = 0;
    next[0] = 0;
    for (int i = 1; i < str.size(); i++) {
        //前后缀不相同怎么处理
        while (j > 0 && str[i] != str[j]) j = next[j - 1];
        //前后缀相同怎么处理
        if (str[i] == str[j]) j++;     
        
        next[i] = j;
    }
}
int kmp(const string& str, const string& ptr, const int* next) {
    int j = 0;
    for (int i = 0; i < str.size(); i++) {
        while (j > 0 && str[i] != ptr[j])j = next[j - 1];
        if (str[i] == ptr[j])j++;
        if (j == ptr.size())return i - j + 1;
    }
    return -1;
}
int main() {
    string str = "ababcababcababdababcababa";
    string ptr = "ababcababa";
    int next[13] = { 0 };
    get_next(ptr, next);
    cout << kmp(str, ptr, next);
}

4 二分查找算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
##include <iostream>
using namespace std;

int main()
{
	int a[] = { 1,2,4,6,12,13,18,22,28,31 };
	int key = 31;//查找关键字
	int low = 0;
	int high = sizeof(a)/sizeof(a[0]);

	while (low <= high) {
		int mid = (low + high) / 2;
		if (a[mid] == key) {
			cout << "找到" << endl;
			break;
		}
		if (a[mid] > key)high = mid-1;
		else if (a[mid] < key)low = mid+1;
	}
	if (low > high)cout << "未找到" << endl;
	return 0;
}

5 深度优先搜索【DFS】

在一个 w×h 的矩形广场上，每一块 1×1 的地面都铺设了红色或黑色的瓷砖。小林同学站在某一块黑色的瓷砖上，他可以从此处出发，移动到上、下、左、右四个相邻的且是黑色的瓷砖上。现在，他想知道，通过重复上述移动所能经过的黑色瓷砖数。

【输入格式】

第 1 行为 h、w，2≤w、h≤50，之间由一个空格隔开。

以下为一个 w 行 h 列的二维字符矩阵，每个字符为“.”“#”“@”，分别表示该位置为黑色的瓷砖、红色的瓷砖，以及小林的初始位置。

【输出格式】

输出一行一个整数，表示小林从初始位置出发可以到达的瓷砖数。

【输入输出样例】

11 9

.#.........

.#.#######.

.#.#.....#.

.#.#.###.#.

.#.#..@#.#.

.#.#####.#.

.#.......#.

.#########.

...........

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
using namespace std;
int m, n, x, y, nx, ny, sum = 1;
int cx[4] = { 0,0,1,-1 };
int cy[4] = { 1,-1,0,0 };
char ma[23][23];
int mo[23][23];
void dfs(int sx, int sy)
{
	for (int i = 0; i < 4; i++)
	{
		nx = sx + cx[i];
		ny = sy + cy[i];
		if (nx >= 0 && nx <= m && ny >= 0 && ny <= n && mo[nx][ny] == 0 && ma[nx][ny] == '.')
		{
			sum++;
			mo[nx][ny] = 1;
			dfs(nx, ny);
			mo[nx][ny] = 0;
		}
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> ma[i][j];
			if (ma[i][j] == '@')
			{
				x = i;
				y = j;
			}
		}
	}
	dfs(x, y);

	cout << sum;
	return 0;
}

6 广度优先搜索【BFS】

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
27
28
int cx[4]={0,0,-1,1};
int cy[4]={1,-1,0,0};
int bfs(int sx,int sy){
    int cnt = 0;
    q.push(node{sx,sy,0});//压入队列
    
    while(!q.empty()){//队列不为空
        node p=q.top();//取出队列第一个元素
        q.pop();//弹出
        if(p.x == ex,p.y == ey){//找到终点然后直接返回路径的长度
            return p.k;
        }
        
        if(vis[p.x][p.y]) continue;//已去过
        
        vis[p.x][p.y] = true;//标记已去过
        
        for(int i=0;i < 4;++i){
            int nx = x + cx[i];
            int ny = y + cy[i];
            if( check(nx,ny) ){
                q.push(node{nx,ny,p.k+1});
            }
        }
    }
    return -1;//没有路径的
}