算法与数据结构
先给出这里会用到的一些工具的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <iostream>
#include <vector>
#include <ctime>
#include <random>
using namespace std;
void getRandomNum(vector<int> &nums, int maxSize, int maxValue) {
default_random_engine e;
uniform_real_distribution<double> u(0.0, 1.0);
e.seed( time(0) );
nums.clear();
int len = (int)(maxSize + 1)*(u(e));
for (int i = 0; i < len; i++){
int temp = (int)((maxValue + 1)*(u(e))) - (int)((maxValue)*(u(e)));
// int temp = rand() % 100;
nums.push_back(temp);
}
return;
}
|
排序算法
选择排序
假设要将数组按照升序排序则算法每次循环都选择一个最小值放在当前的位置处，初始位置应为0，每次循环结束都+1到下一位置，重复此过程到结束，这就是选择排序，选某个值放在某个地方。比如一个数组int a[5] = {2, 3, 1, 0, 4}使用选择排序做到整体有序首先从a[0]开始，寻找下标$[0, 4]$中的最小值，找到为0，最小值下标为3，则将下标为0的和下标为3的元素交换，然后到a[1]继续寻找$[1, 4]$的最小值并和a[1]交换，重复此过程到a[4]结束循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void selectionSort(vector<int> &nums) {
int n = nums.size();
if (n < 2) {
return;
}
int min = INT_MAX;
int index = 0;
for (int i = 0; i < n; ++i) { // 外层for循环，表示最后min要放在哪
for (int j = i; j < n; ++j) { // 内层for循环，找从i~n-1的最小值
if (nums[j] < min) {
min = nums[j];
index = j;
}
}
swap(nums[i], nums[index]); // 最后把最小值放到i位置，但是不能覆盖啊，不然i位置的就丢了，那就交换吧
}
}
|
画个图就是：
此排序算法的时间复杂度为O(n^2^)，两层for循环浪费了太多时间比较大小。而且不能做到稳定，因为在swap的过程可能破坏稳定性。
冒泡排序
依然假设要将数组升序排序则这里有两种想法：① 把最大的往后移；② 把最小的往前移。这里就看看把最大的往后移，比较常见，会了这个第二个也很简单。首先从$i=n-1$（n表示数组元素个数）下标位置开始；啥？为啥是$n-1$，因为要把大的往后移，这里就相当于最后最大的那个数该放的位置了。
然后再for循环从0到$i-1$开始做以下操作：
- 看看当前元素和下一个元素大小关系
- 下一个大则交换他俩位置在到下一个元素，否则直接到下一个
- 继续比较直到结束循环
为啥这会又是$i-1$呢，因为最后一个元素没有下一个了。比如刚刚那个数组int a[5] = {2, 3, 1, 0, 4}使用冒泡排序升序排序过程就是：首先$i=4$，然后j从0开始，$a[j]=2<a[j+1]=3$所以j直接加1，然后此时$a[j]=3>a[j+1]=1$所以交换他俩后$a[j]=1,a[j+1]=3$然后加1最后数组a会变[2, 1, 0, 3, 4]然后一直循环最后整体就会有序。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void bubbleSort(vector<int> &nums) {
int n = nums.size();
if (n < 2) {
return;
}
for (int i = n - 1; i > 0; --i) {
for (int j = 0; j < i; ++j) {
if (nums[j] > nums[j + 1]) {
swap(nums[j], nums[j + 1]);
}
}
}
}
|
画个图就是这样子：
最后i的位置一定是本次循环最大的那个，因为最大的数一直往上换，就想冒泡一样往上冒，然后到i那去了。此算法的时间复杂度也是O(n^2^)，他也浪费了大把时间在做比较，很多比较都重复了，没有利用起来。不过冒泡可以做到稳定性，他可以设置只有num[j]严格大于nums[j + 1]才做交换，这样相等的数的先后顺序没有变化，稳定性没有被破坏。
插入排序
还是熟悉的升序排列数组，
归并排序
要学习归并首先要了解递归，递归就是函数调用自身的过程。利用递归我们可以将一个复杂的问题转化为更简单的子问题，求解子问题最终得到答案。归并排序的思想就是将待排序的数组一分为二，对左右两边操作使其分别有序，最后合并两部分，使得整体有序，其具体实现如下：
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
#include <iostream>
#include <vector>
#include <algorithm>
#include "getRandomArray.cpp"
using namespace std;
/*
归并排序（递归方式实现）：
三个函数，其作用分别为
- mergeSort()算法入口函数
- process()递归过程函数
- merge()合并函数
算法将一个整体数组分为左右两部分，经过一系列操作使得左右两部分
分别有序，最后将左右两部分合并在一起使得整体有序，用到了分治思
想，将整体大的问题分解为子问题，求解子问题最后得到大问题。
*/
void mergeSort(vector<int> &nums);
void process(vector<int> &nums, int l, int r);
void merge(vector<int> &nums, int l, int m, int r);
int main()
{
int maxtimes = 10000; // 测试次数
int maxsize = 1000; // 数组最大长度
int maxvalue = 1000; // 数组最大绝对值
vector<int> nums1;
vector<int> nums2;
for (int i = 0; i < maxtimes; ++i) {
getRandomNum(nums1, maxsize, maxvalue);
nums2 = nums1;
mergeSort(nums1);
sort(nums2.begin(), nums2.end());
if (nums2 != nums1) {
cout << "shit!!!" << endl;
return 0;
}
}
cout << "nice!!!" << endl;
return 0;
}
void mergeSort(vector<int> &nums) {
if (nums.size() < 2) {
return;
}
process(nums, 0, nums.size() - 1);
}
void process(vector<int> &nums, int l, int r) {
// 递归的出口条件
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);
process(nums, l, mid);
process(nums, mid + 1, r);
// 左右两侧都有序，可以合并
merge(nums, l, mid, r);
}
void merge(vector<int> &nums, int l, int m, int r) {
// 辅助数组，用于合并，其大小和传入的一致
vector<int> help(r - l + 1, 0);
int i = 0; // 辅助数组的指针
int p1 = l, p2 = m + 1; // 两侧数组的指针
while (p1 <= m && p2 <= r) {
help[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
}
// 走到这里说明p1、p2必有一个越界了，此时需要将未越界一侧剩下的拷贝
while(p1 <= m) {
help[i++] = nums[p1++];
}
while(p2 <= r) {
help[i++] = nums[p2++];
}
for (i = 0; i < r - l + 1; ++i) {
nums[i + l] = help[i];
}
}
|
图
图的存储方式
图的存储方式多种多样，这里记两种常见的
1）邻接表
无向图：由节点和边组成（边可以有权值）
有向图类似
2）邻接矩阵
假设将上图加上权值：
则其临界矩阵表示为：（矩阵中每个值表示边的权，无穷表示没有边）
Code
图结构：（邻接表）
1
2
3
4
5
6
7
|
class Graphic {
public:
unordered_map<int, Node*> *m_nodes; // 点集，int表示点的编号，Node是本身的点结构
unordered_set<int> *m_sets; // 边集，int表示边的权值
Graphic() : m_nodes(new unordered_map<int, Node*>()), m_sets(new unordered_set<int>()){}
};
|
点结构：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Node {
public:
int m_value; // 值，当然何以考虑设计成template
int m_in; // 入度
int m_out; // 出度
vector<Node*> *m_nexts; // 相当于邻接表中的邻居
vector<Edge*> *m_edges; // 该节点的所有边
Node() {
m_value = 0;
m_in = 0;
m_out = 0;
m_nexts = new vector<Node*>();
m_edges = new vector<Edge*>();
}
};
|
边结构：
1
2
3
4
5
6
7
8
9
10
11
12
|
class Edge {
public:
int m_weight; // 权重
Node *m_from; // 从哪
Node *m_to; //到哪
Edge(int weight, Node *from, Node *to) {
m_weight = weight;
m_from = from;
m_to = to;
}
};
|
具体解题的时候可以根据题目给的图结构实现接口函数。这里以二维矩阵为例，假设矩阵的每一行都是一个长度为3的数组，第一个元素表示from点，第二个元素表示to点，第三个元素表示权重，则接口函数可实现成：
广度优先搜索：（BFS）
对于这样一个无向图：
假设从A开始则其广度优先算法结果差不多为A->B->C->D->E，我们需要借助队列实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
void bfs(Node *node) {
if (node == nullptr) {
return;
}
queue<node*> que = new queue<node*>(); // 辅助队列
unordered_set<node*> set = new unordered_set<node*>; // 防止node重复入队
que.push(node);
set.insert(node);
// 开始广度优先搜索
while(!queue.empty()) {
Node *cur = que.front();
que.pop();
for (const auto &item : cur->m_nexts) {
if (set.find(item) == set.end()) {
set.insert(item);
que.push(item);
}
}
}
}
|
深度优先搜索：（DFS）
对于同样的图，DFS的结果可以为A->B->E->D->C（在有向图中可能不明显），我们需要借助栈实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
void dfs(Node *node) {
if (node == nullptr) {
return;
}
stack<Node*> stack = new stack<Node*>(); // 栈存放深度优先搜索的路径
unordered_set<Node*> set = new unordered_set<Node*>(); // 集合表示已经搜索过的
stack.push(node);
set.insert(node);
cout << node->m_value << endl; // 处理过程
while (!stack.empty()) {
Node *cur = stack.top();
stack.pop();
for (Node *next : cur->m_nexts) {
if (set.find(next) == set.end()) {
stack.push(cur);
stack.push(next);
set.insert(next);
cout << next->m_value << endl; // 处理过程
break;
}
}
}
}
|
拓扑排序：
