13 行代码C++工具函数
方向数组
二维数组枚举、BFS/DFS 常用的方向数组
// 上下左右四方向
int dx4[] = {-1, 1, 0, 0};
int dy4[] = {0, 0, -1, 1};
// 上下左右、左上右上、左下右下八方向
int dx8[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dy8[] = {0, 0, -1, 1, -1, 1, -1, 1};#方向数组#枚举
二维数组枚举、BFS/DFS 常用的方向数组
// 上下左右四方向
int dx4[] = {-1, 1, 0, 0};
int dy4[] = {0, 0, -1, 1};
// 上下左右、左上右上、左下右下八方向
int dx8[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dy8[] = {0, 0, -1, 1, -1, 1, -1, 1};汇总一下三大基础排序算法的写法以及时间空间复杂度、稳定性
1-based 下标的冒泡排序,时间复杂度 O(n²),空间 O(1),稳定
// 升序,数组下标从 1 开始,有效范围为 a[1] ~ a[n]
void bubble_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
bool flag = true;
for (int j = 1; j <= n - i; j++)
if (a[j] > a[j + 1]) {1-based 下标的插入排序,时间复杂度 O(n²),空间 O(1),稳定
// 升序,数组下标从 1 开始,有效范围为 a[1] ~ a[n]
// 1. 后移法
void insert_sort1(int a[], int n) {
for (int i = 2; i <= n; i++) {
int key = a[i];1-based 下标的选择排序,时间复杂度 O(n²),空间 O(1),不稳定
// 升序,数组下标从 1 开始,有效范围为 a[1] ~ a[n]
void select_sort(int a[], int n) {
for (int i = 1; i < n; i++){
int idx = i;
for (int j = i+1; j <= n; j++) {
if (a[j] < a[idx])二维数组枚举、BFS/DFS 常用的方向数组技巧