当涉及到常见的算法示例时，以下是一些常见的 C++ 算法及其示例：
1. **排序算法**：
- 冒泡排序
- 选择排序
- 插入排序
- 归并排序
- 堆排序
- 计数排序
- 桶排序
- 基数排序
2. **搜索算法**：
- 线性搜索
- 二分查找
- 深度优先搜索（DFS）
- 广度优先搜索（BFS）
3. **字符串处理算法**：
- 字符串反转
- 字符串查找
- 字符串替换
- 字符串拼接
- 字符串分割
4. **图算法**：
- 最短路径算法（如 Dijkstra 算法、Floyd-Warshall 算法）
- 最小生成树算法（如 Prim 算法、Kruskal 算法）
- 拓扑排序算法
- 深度优先搜索（DFS）和广度优先搜索（BFS）
5. **动态规划算法**：
- 斐波那契数列
- 背包问题
- 最长公共子序列问题
- 最长递增子序列问题
6. **贪心算法**：
- 部分背包问题
- 区间调度问题
- 霍夫曼编码
1. **冒泡排序**：
```cpp
#include <iostream>
#include <vector>
void bubbleSort(std::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]) {
std::swap(arr[j], arr[j+1]);
}
}
}
}
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
for (int num : arr) {
std::cout << num << " ";
}
return 0;
}
```
2. **选择排序**：
```cpp
#include <iostream>
#include <vector>
void selectionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n-1; i++) {
int min_index = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
std::swap(arr[i], arr[min_index]);
}
}
int main() {
std::vector<int> arr = {64, 25, 12, 22, 11};
selectionSort(arr);
for (int num : arr) {
std::cout << num << " ";
}
return 0;
}
```
3. **插入排序**：
```cpp
#include <iostream>
#include <vector>
void insertionSort(std::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;
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
insertionSort(arr);
for (int num : arr) {
std::cout << num << " ";
}
return 0;
}
```
4. **归并排序**：
```cpp
#include <iostream>
#include <vector>
void merge(std::vector<int>& arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
std::vector<int> L(n1), R(n2);
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(std::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);
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
mergeSort(arr, 0, arr.size() - 1);
for (int num : arr) {
std::cout << num << " ";
}
return 0;
}
```
5. **堆排序**：
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
void heapify(std::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) {
std::swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(std::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--) {
std::swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
heapSort(arr);
for (int num : arr) {
std::cout << num << " ";
}
return 0;
}
```
1. **线性搜索**：
```cpp
#include <iostream>
#include <vector>
int linearSearch(std::vector<int>& arr, int target) {
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == target) {
return i;
}
}
return -1; // 未找到目标值
}
int main() {
std::vector<int> arr = {2, 5, 7, 9, 12, 15};
int target = 7;
int index = linearSearch(arr, target);
if (index != -1) {
std::cout << "目标值在数组中的索引为：" << index << std::endl;
} else {
std::cout << "未找到目标值。" << std::endl;
}
return 0;
}
```
2. **二分查找**：
```cpp
#include <iostream>
#include <vector>
int binarySearch(std::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() {
std::vector<int> arr = {2, 5, 7, 9, 12, 15};
int target = 7;
int index = binarySearch(arr, target);
if (index != -1) {
std::cout << "目标值在数组中的索引为：" << index << std::endl;
} else {
std::cout << "未找到目标值。" << std::endl;
}
return 0;
}
```
1. **最短路径算法 - Dijkstra算法**：
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#define INF std::numeric_limits<int>::max()
void dijkstra(std::vector<std::vector<std::pair<int, int>>>& graph, int start) {
int n = graph.size();
std::vector<int> dist(n, INF);
dist[start] = 0;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
pq.push({0, start});
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (auto& edge : graph[u]) {
int v = edge.first;
int weight = edge.second;
if (dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
for (int i = 0; i < n; i++) {
std::cout << "从节点 " << start << " 到节点 " << i << " 的最短距禿：" << dist[i] << std::endl;
}
}
int main() {
int n = 5;
std::vector<std::vector<std::pair<int, int>>> graph(n);
graph[0].push_back({1, 4});
graph[0].push_back({2, 1});
graph[1].push_back({3, 1});
graph[2].push_back({1, 2});
graph[2].push_back({3, 5});
graph[3].push_back({4, 3});
dijkstra(graph, 0);
return 0;
}
```
2. **最小生成树算法 - Prim算法**：
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#define INF std::numeric_limits<int>::max()
void prim(std::vector<std::vector<std::pair<int, int>>>& graph) {
int n = graph.size();
std::vector<bool> visited(n, false);
std::vector<int> dist(n, INF);
dist[0] = 0;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
pq.push({0, 0});
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
visited[u] = true;
for (auto& edge : graph[u]) {
int v = edge.first;
int weight = edge.second;
if (!visited[v] && dist[v] > weight) {
dist[v] = weight;
pq.push({dist[v], v});
}
}
}
int minCost = 0;
for (int d : dist) {
minCost += d;
}
std::cout << "最小生成树的总权值为：" << minCost << std::endl;
}
int main() {
int n = 5;
std::vector<std::vector<std::pair<int, int>>> graph(n);
graph[0].push_back({1, 2});
graph[0].push_back({3, 6});
graph[1].push_back({0, 2});
graph[1].push_back({2, 3});
graph[1].push_back({3, 8});
graph[2].push_back({1, 3});
graph[3].push_back({0, 6});
graph[3].push_back({1, 8});
prim(graph);
return 0;
}
```
1. **部分背包问题**：
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
struct Item {
int value;
int weight;
};
bool compare(Item a, Item b) {
double ratio1 = (double)a.value / a.weight;
double ratio2 = (double)b.value / b.weight;
return ratio1 > ratio2;
}
double fractionalKnapsack(int capacity, std::vector<Item>& items) {
std::sort(items.begin(), items.end(), compare);
double maxValue = 0.0;
for (const Item& item : items) {
if (capacity == 0) {
break;
}
int weightToAdd = std::min(item.weight, capacity);
maxValue += weightToAdd * ((double)item.value / item.weight);
capacity -= weightToAdd;
}
return maxValue;
}
int main() {
int capacity = 50;
std::vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};
double maxTotalValue = fractionalKnapsack(capacity, items);
std::cout << "最大总价值为：" << maxTotalValue << std::endl;
return 0;
}
```
2. **区间调度问题**：
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
struct Interval {
int start;
int end;
};
bool compareEnd(Interval a, Interval b) {
return a.end < b.end;
}
int intervalScheduling(std::vector<Interval>& intervals) {
if (intervals.empty()) {
return 0;
}
std::sort(intervals.begin(), intervals.end(), compareEnd);
int count = 1;
int end = intervals[0].end;
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i].start >= end) {
count++;
end = intervals[i].end;
}
}
return count;
}
int main() {
std::vector<Interval> intervals = {{1, 3}, {2, 4}, {3, 6}, {5, 7}, {8, 9}};
int minRooms = intervalScheduling(intervals);
std::cout << "需要的最小会议室数量为：" << minRooms << std::endl;
return 0;
}
```