从基础到进阶：一文掌握排序、查找、动态规划与图算法的全面实现（C++代码实例解析）

引言

算法是计算机科学的核心，也是程序员解决复杂问题的利器。从基础的排序与查找到进阶的动态规划与图论算法，掌握这些技能不仅是提升编程能力的必经之路，更是解决实际问题的根本。本篇文章将通过 C++ 实现多个经典算法，包括排序、二分查找、动态规划、深度优先搜索（DFS）与 Dijkstra 最短路径算法，助你从基础入门到进阶精通。

第一部分：基础算法篇

1.1 冒泡排序：从无序到有序的第一步

冒泡排序是一个简单的排序算法，通过不断比较相邻元素并交换位置，将较大的元素“冒泡”到右侧。

代码实现：

#include <iostream>
#include <vector>
using namespace std;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]);}}}
}int main() {vector<int> arr = {64, 34, 25, 12, 22, 11, 90};cout << "排序前的数组: ";for (int num : arr) cout << num << " ";cout << endl;bubbleSort(arr);cout << "排序后的数组: ";for (int num : arr) cout << num << " ";cout << endl;return 0;
}

1.2 二分查找：高效定位目标的秘诀

二分查找是一种高效的查找算法，适用于有序数组。通过逐步缩小查找范围，可以在 O(log⁡n)O(logn) 的时间复杂度内定位目标值。

代码实现：

#include <iostream>
#include <vector>
using namespace std;int binarySearch(const vector<int>& arr, int target) {int left = 0, right = arr.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) return mid;else if (arr[mid] < target) left = mid + 1;else right = mid - 1;}return -1; // 未找到目标
}int main() {vector<int> arr = {2, 3, 4, 10, 40};int target = 10;int result = binarySearch(arr, target);if (result != -1) {cout << "目标值 " << target << " 在索引 " << result << " 处" << endl;} else {cout << "目标值 " << target << " 未找到" << endl;}return 0;
}

第二部分：进阶算法篇

2.1 动态规划：解决 0/1 背包问题

动态规划是一种通过记录子问题结果来避免重复计算的优化算法。在 0/1 背包问题中，我们利用动态规划求解在给定背包容量下，如何选择物品以最大化价值。

代码实现：

#include <iostream>
#include <vector>
using namespace std;int knapsack(int W, const vector<int>& weight, const vector<int>& value, int n) {vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));for (int i = 1; i <= n; i++) {for (int w = 1; w <= W; w++) {if (weight[i - 1] <= w) {dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight[i - 1]] + value[i - 1]);} else {dp[i][w] = dp[i - 1][w];}}}return dp[n][W];
}int main() {int W = 50;vector<int> weight = {10, 20, 30};vector<int> value = {60, 100, 120};int n = weight.size();cout << "背包的最大价值: " << knapsack(W, weight, value, n) << endl;return 0;
}

2.2 图算法：Dijkstra 最短路径

Dijkstra 是经典的单源最短路径算法，适合无负权边的图。我们通过优先队列实现高效的路径计算。

代码实现：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;const int INF = INT_MAX;void dijkstra(int start, const vector<vector<pair<int, int>>>& graph, vector<int>& distance) {int n = graph.size();distance.assign(n, INF);distance[start] = 0;priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;pq.push({0, start});while (!pq.empty()) {int currentDist = pq.top().first;int currentNode = pq.top().second;pq.pop();if (currentDist > distance[currentNode]) continue;for (auto& edge : graph[currentNode]) {int nextNode = edge.first;int weight = edge.second;if (distance[currentNode] + weight < distance[nextNode]) {distance[nextNode] = distance[currentNode] + weight;pq.push({distance[nextNode], nextNode});}}}
}int main() {int n = 5;vector<vector<pair<int, int>>> graph(n);graph[0].push_back({1, 10});graph[0].push_back({4, 5});graph[1].push_back({2, 1});graph[2].push_back({3, 4});graph[4].push_back({1, 3});graph[4].push_back({2, 9});graph[4].push_back({3, 2});vector<int> distance;dijkstra(0, graph, distance);cout << "从节点 0 出发到其他节点的最短距离: " << endl;for (int i = 0; i < distance.size(); i++) {cout << "节点 0 到节点 " << i << " 的距离: " << (distance[i] == INF ? -1 : distance[i]) << endl;}return 0;
}