std::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);
    }
}

神秘代码

神秘小代码·ONE

#include <iostream>
#include <random>
using namespace std;
char a[3];
int main() {
	a[0] = '0';
	a[1] = '1';
	a[2] = ' ';
	random_device rd;
	mt19937 gen(rd());
	uniform_int_distribution<int> distribution(0, 2);
	while (true) {
		int index = distribution(gen);
		cout << a[index];
	}
	return 0;
}    

神秘小代码·TWO：

#include <iostream>
#include <random>
#include <chrono>

using namespace std;

int main() {
    const int CHARACTER_COUNT = 3;
    char display_symbols[CHARACTER_COUNT] = {'0', '1', ' '};
    
    const int MIN_INDEX = 0;
    const int MAX_INDEX = 2;

    unsigned long seed_value = chrono::system_clock::now().time_since_epoch().count();
    mt19937 random_generator(seed_value);
    uniform_int_distribution<int> index_selector(MIN_INDEX, MAX_INDEX);

    while (true) {
        int random_position = index_selector(random_generator);
        char selected_character = display_symbols[random_position];
        cout << selected_character;
    }

    return 0;
}