C 与 C++ 算法实战全景

C 与 C++ 的算法体系体现了系统级编程从底层指针操作到**现代泛型概念（Concepts/Ranges）**的演进：

C 语言：依靠函数指针（如 qsort、bsearch）和 void* 内存跨度实现多态。
C++ (C++20)：通过 std::ranges、迭代器双端抽象、Lambda 闭包与 STL 算法库实现强类型安全、内联优化与零运行时损耗。

📊 核心算法分类与复杂度

算法专题	经典问题 / 算法	核心思想	时间复杂度	空间复杂度
排序	QuickSort / `std::sort`	分治划分、内省排序 (Introsort)	平均 $O(n \log n)$，最坏 $O(n^2)$	$O(\log n)$ 递归栈
二分查找	`std::lower_bound` / `std::upper_bound`	单调性折半搜索	$O(\log n)$	$O(1)$
图遍历	BFS / DFS	队列层序扩展 / 递归回溯	$O(V + E)$	$O(V)$
最短路径	Dijkstra 算法	贪心选择 + 优先队列 (Min-Heap) 松弛边	$O((V + E) \log V)$	$O(V)$
连通性	并查集 (Union-Find)	路径压缩 + 按秩合并	接近反阿克曼 $O(\alpha(n))$	$O(V)$
动态规划	0/1 背包问题	状态定义、无后效性转移、空间压缩 (1D Array)	$O(N \cdot W)$	优化后 $O(W)$

1. 排序算法：快速排序与内省排序 (Introsort)

C++20 `std::sort` 与快速排序实现

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

int main() {
    std::cout << "=== C++ std::sort (Introsort) & QuickSort ===" << std::endl;
    std::vector<int> vec = {64, 25, 12, 22, 11};
    std::sort(vec.begin(), vec.end());

    assert(std::is_sorted(vec.begin(), vec.end()));
    assert((vec[0] == 11 && vec[4] == 64));

    std::cout << "Sorted result: ";
    for (int v : vec) std::cout << v << " ";
    std::cout << "\nC++ Sort tests passed successfully." << std::endl;
    return 0;
}

🐳 Docker Verified📋gcc:13

Exit Code: 0

=== C++ std::sort (Introsort) & QuickSort ===
Sorted result: 11 12 22 25 64 
C++ Sort tests passed successfully.

2. 查找与区间检索：二分查找 (Binary Search)

C++ `std::lower_bound` / `std::upper_bound`

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

int main() {
    std::cout << "=== C++ Binary Search & Bounds ===" << std::endl;
    std::vector<int> arr = {10, 20, 20, 20, 30, 40, 50};

    bool exists = std::binary_search(arr.begin(), arr.end(), 30);
    assert(exists);

    auto lower = std::lower_bound(arr.begin(), arr.end(), 20);
    auto upper = std::upper_bound(arr.begin(), arr.end(), 20);

    assert(std::distance(arr.begin(), lower) == 1);
    assert(std::distance(arr.begin(), upper) == 4);

    std::cout << "Target 20 range count: " << (upper - lower) << std::endl;
    std::cout << "C++ Binary Search tests passed successfully." << std::endl;
    return 0;
}

🐳 Docker Verified📋gcc:13

Exit Code: 0

=== C++ Binary Search & Bounds ===
Target 20 range count: 3
C++ Binary Search tests passed successfully.

3. 图论算法：BFS 遍历、Dijkstra 最短路径与并查集

图的广度优先遍历 (BFS)

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

class Graph {
    int V;
    std::vector<std::vector<int>> adj;
public:
    Graph(int v) : V(v), adj(v) {}
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    std::vector<int> bfs(int start) {
        std::vector<int> order;
        std::vector<bool> visited(V, false);
        std::queue<int> q;

        visited[start] = true;
        q.push(start);

        while (!q.empty()) {
            int u = q.front(); q.pop();
            order.push_back(u);
            for (int v : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.push(v);
                }
            }
        }
        return order;
    }
};

int main() {
    std::cout << "=== C++ Graph BFS Traversal ===" << std::endl;
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);

    auto order = g.bfs(0);
    assert(order.size() == 5);
    assert(order[0] == 0);
    std::cout << "C++ Graph BFS traversal verified." << std::endl;
    return 0;
}

🐳 Docker Verified📋gcc:13

Exit Code: 0

=== C++ Graph BFS Traversal ===
C++ Graph BFS traversal verified.

Dijkstra 单源最短路径 (优先队列优化版)

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

using Edge = std::pair<int, int>;

std::vector<int> dijkstra(int n, int start, const std::vector<std::vector<Edge>>& graph) {
    const int INF = 1e9;
    std::vector<int> dist(n, INF);
    std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;

        for (auto [w, v] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

int main() {
    std::cout << "=== C++ Dijkstra Shortest Path ===" << std::endl;
    int n = 4;
    std::vector<std::vector<Edge>> graph(n);
    graph[0].push_back({1, 1});
    graph[0].push_back({4, 2});
    graph[1].push_back({2, 2});
    graph[2].push_back({1, 3});
    graph[1].push_back({5, 3});

    auto dist = dijkstra(n, 0, graph);
    assert(dist[3] == 4);
    std::cout << "Shortest path to node 3: " << dist[3] << std::endl;
    std::cout << "C++ Dijkstra tests passed successfully." << std::endl;
    return 0;
}

🐳 Docker Verified📋gcc:13

Exit Code: 0

=== C++ Dijkstra Shortest Path ===
Shortest path to node 3: 4
C++ Dijkstra tests passed successfully.

并查集 (Disjoint Set Union / Union-Find)

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <cassert>

class UnionFind {
    std::vector<int> parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        std::iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unite(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return false;
        if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
        else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
        else { parent[rootY] = rootX; rank[rootX]++; }
        return true;
    }
    bool connected(int x, int y) { return find(x) == find(y); }
};

int main() {
    std::cout << "=== C++ Disjoint Set Union (Union-Find) ===" << std::endl;
    UnionFind uf(5);
    uf.unite(0, 1);
    uf.unite(1, 2);
    assert(uf.connected(0, 2));
    assert(!uf.connected(0, 3));
    std::cout << "C++ Union-Find tests passed successfully." << std::endl;
    return 0;
}

🐳 Docker Verified📋gcc:13

Exit Code: 0

=== C++ Disjoint Set Union (Union-Find) ===
C++ Union-Find tests passed successfully.

4. 动态规划：0/1 背包问题

状态转移与 1D 滚动数组空间压缩

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

int knapsack01(int W, const std::vector<int>& weights, const std::vector<int>& values) {
    int n = weights.size();
    std::vector<int> dp(W + 1, 0);

    for (int i = 0; i < n; ++i) {
        for (int w = W; w >= weights[i]; --w) {
            dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

int main() {
    std::cout << "=== C++ 0/1 Knapsack Dynamic Programming ===" << std::endl;
    std::vector<int> weights = {2, 3, 4, 5};
    std::vector<int> values = {3, 4, 5, 6};
    int W = 5;

    int max_val = knapsack01(W, weights, values);
    assert(max_val == 7);

    std::cout << "Max knapsack value for W=5: " << max_val << std::endl;
    std::cout << "C++ Knapsack DP tests passed successfully." << std::endl;
    return 0;
}

🐳 Docker Verified📋gcc:13

Exit Code: 0

=== C++ 0/1 Knapsack Dynamic Programming ===
Max knapsack value for W=5: 7
C++ Knapsack DP tests passed successfully.

C 与 C++ 算法实战全景 ​

📊 核心算法分类与复杂度 ​

1. 排序算法：快速排序与内省排序 (Introsort) ​

C++20 std::sort 与快速排序实现 ​

2. 查找与区间检索：二分查找 (Binary Search) ​

C++ std::lower_bound / std::upper_bound ​

3. 图论算法：BFS 遍历、Dijkstra 最短路径与并查集 ​

图的广度优先遍历 (BFS) ​

Dijkstra 单源最短路径 (优先队列优化版) ​

并查集 (Disjoint Set Union / Union-Find) ​

4. 动态规划：0/1 背包问题 ​

状态转移与 1D 滚动数组空间压缩 ​

C 与 C++ 算法实战全景

📊 核心算法分类与复杂度

1. 排序算法：快速排序与内省排序 (Introsort)

C++20 `std::sort` 与快速排序实现

2. 查找与区间检索：二分查找 (Binary Search)

C++ `std::lower_bound` / `std::upper_bound`

3. 图论算法：BFS 遍历、Dijkstra 最短路径与并查集

图的广度优先遍历 (BFS)

Dijkstra 单源最短路径 (优先队列优化版)

并查集 (Disjoint Set Union / Union-Find)

4. 动态规划：0/1 背包问题

状态转移与 1D 滚动数组空间压缩