深度优先搜索

#include <bits/stdc++.h>
using namespace std;
int a[10][10];
void dfs(int x,int y,int k) {
	a[x][y] = k;
	if (y + 1 <= 4 && a[x][y+1] == 0){
		dfs(x,y+1,k+1);
	}
	if (x + 1 <= 4 && a[x+1][y] == 0){
		dfs(x+1,y,k+1);
	}
	if (y - 1 >= 1 && a[x][y-1] == 0){
		dfs(x,y-1,k+1);
	}
	if (x - 1 >= 1 && a[x-1][y] == 0){
		dfs(x-1,y,k+1);
	}
}
int main() {
	dfs(1,1,1);
	for (int i = 1;i <= 4;i++) {
		for (int j = 1;j <= 4;j++) {
			cout << setw(5) << a[i][j];
		}
		cout << endl;
	}
}

sort (快速排序/内省排序)

时间复杂度：O(N log N)‌

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    vector<int> v = {5, 3, 1, 4, 2};
    // 默认升序排序
    sort(v.begin(), v.end());
    // 降序排序
    sort(v.begin(), v.end(), greater<int>());
    // 自定义比较函数
    sort(v.begin(), v.end(), [](int a, int b) {
        return a % 3 < b % 3;
    });
    return 0;
}

基础排序算法

冒泡排序

时间复杂度：O(N²)‌

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

选择排序

时间复杂度：O(N²)‌

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        swap(arr[i], arr[min_idx]);
    }
}

插入排序

时间复杂度：O(N²)‌

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

高效排序算法

归并排序

时间复杂度：O(N log N)‌

void merge(vector<int>& arr, int l, int m, int r) {
    vector<int> temp(r - l + 1);
    int i = l, j = m+1, k = 0;
    
    while (i <= m && j <= r) {
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= m) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];
    
    for (int p = 0; p < temp.size(); p++) {
        arr[l + p] = temp[p];
    }
}

void mergeSort(vector<int>& arr, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

快速排序

时间复杂度：平均 O(N log N)，最坏 O(N²)‌

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

特殊排序算法

桶排序

时间复杂度：O(N + k)‌

void bucketSort(vector<float>& arr) {
    int n = arr.size();
    vector<vector<float>> buckets(n);
    
    for (int i = 0; i < n; i++) {
        int bi = n * arr[i];
        buckets[bi].push_back(arr[i]);
    }
    
    for (int i = 0; i < n; i++) {
        sort(buckets[i].begin(), buckets[i].end());
    }
    
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < buckets[i].size(); j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

堆排序

时间复杂度：O(N log N)‌

void heapify(vector<int>& arr, int n, int i) {
    int largest = i;
    int l = 2*i + 1;
    int r = 2*i + 2;
    
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();
    
    for (int i = n/2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    for (int i = n-1; i > 0; i--) {
        swap(arr, arr[i]);
        heapify(arr, i, 0);
    }
}

神秘代码

神秘小代码 C++17(O2)

#include <iostream>
#include <random>
#include <array>
#include <string_view>
using namespace std;
int main() {
    constexpr array<string_view, 3> yh = {"1", "0", " "};
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(0, 2);
    while (true) {
        cout << yh[dis(gen)] << ' ';
    } 
    return 0;
}

神秘小代码 Java：

import java.util.Random;
public class RandomPrint {
    public static void main(String[] args) {
        String[] yh = {"1", "0", " "};
        Random random = new Random();
        while (true) {
            int r = random.nextInt(3); 
            System.out.print(yh[r] + " ");
        }
    }
}

神秘小代码 C：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main() {
    char yh[] = {'1', '0', ' '};
    srand(time(NULL));
    while(1) {
        int r = rand() % 3;  
        printf("%c ", yh[r]);
    }
    return 0;
}

神秘小代码 B：

main() {
    extrn putchar, rand;
    auto r;
    while (1) {
        r = rand() % 3;
        if (r == 0) putchar('1');
        if (r == 1) putchar('0');
        if (r == 2) putchar(' ');
        putchar(' ');
    }
}

神秘小代码 Python：

import random
yh=["1","0"," "]
while True:
    r = random.randint(0,2)
    print(yh[r],end=' ')