基础排序算法

插入排序

插入排序（代码填空）

#include <vector>
using namespace std;

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

冒泡排序

冒泡排序（代码填空）

#include <vector>
using namespace std;

void bubble_sort(vector<int> &a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

选择排序

选择排序（代码填空）

#include <vector>
using namespace std;

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

计数排序

计数排序（代码填空）

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

// 计数排序函数
void counting_sort(vector<int>& a) {
    if (a.empty()) return;

    // 找到数组中的最大值
    int maxv = a[0];
    for (int i = 1; i < a.size(); i++) {
        maxv = max(maxv, a[i]);
    }

    // 创建计数数组并初始化
    vector<int> count(maxv + 1, 0);

    // 统计每个元素的出现次数
    for (int i = 0; i < a.size(); i++) {
        count[a[i]]++;
    }

    // 根据计数数组重新排序
        int idx = 0;
    for (int i = 0; i <= maxv; i++) {
        while (count[i] > 0) {
            a[idx++] = i;
            count[i]--;
        }
    }
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        vector<int> a;
        for (int i = 0; i < n; i++) {
            int x;
            scanf("%d", &x);
            a.push_back(x);
        }
        counting_sort(a);
        for (int i = 0; i < n; i++) {
            printf("%d%c", a[i], (i == n - 1) ? '\n' : ' ');
        }
    }
    return 0;
}

基数排序

最后的排序

[!warning] TODO

添加算法解释

#include <vector>
using namespace std;

void my_sort(vector<int> &a) {
	const int base = 65536;
    int n = a.size();
    vector<int> b(n);
    vector<int> c(base, 0);
    for (int exp = 1; exp <= base; exp *= base) {
        for (int i = 0; i < a.size(); i++) {
            c[a[i] / exp % base]++;
        }
        for (int i = 1; i < base; i++) {
            c[i] += c[i - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
            b[--c[a[i] / exp % base]] = a[i];
        }
        swap(a, b);
        for (int i = 0; i < base; i++) {
            c[i] = 0;
        }
    }
}

排序题目

反向字典