在计算机科学中，算法是解决问题的核心。无论是排序、搜索、还是图论问题，掌握和理解各种算法对于编程能力的提升至关重要。本文将通过C++编程语言实现多个具体算法，包括快速排序、二分查找、深度优先搜索（DFS）、广度优先搜索（BFS）以及Dijkstra最短路径算法。这些算法在各类编程竞赛和实际应用中都非常常见。
一、快速排序（Quick Sort）
快速排序是一种高效的排序算法，采用分治法（Divide and Conquer）策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。
#include <iostream>
#include <vector>// 辅助函数，用于交换两个元素
void swap(int& a, int& b) {int temp = a;a = b;b = temp;
}// 分区函数，返回枢轴的位置
int partition(std::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(std::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);}
}int main() {std::vector<int> arr = {10, 7, 8, 9, 1, 5};int n = arr.size();quickSort(arr, 0, n - 1);std::cout << "Sorted array: ";for (int i = 0; i < n; ++i) {std::cout << arr[i] << " ";}std::cout << std::endl;return 0;
}二、二分查找（Binary Search）
二分查找是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。
#include <iostream>
#include <vector>// 二分查找函数，返回目标元素的索引，若不存在则返回-1
int binarySearch(const 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;}// 如果目标元素大于mid元素，则忽略左半部分if (arr[mid] < target) {left = mid + 1;} else { // 如果目标元素小于mid元素，则忽略右半部分right = mid - 1;}}// 目标元素不存在于数组中return -1;
}int main() {std::vector<int> arr = {2, 3, 4, 10, 40};int target = 10;int result = binarySearch(arr, target);if (result != -1) {std::cout << "Element found at index " << result << std::endl;} else {std::cout << "Element not found in array" << std::endl;}return 0;
}三、深度优先搜索（DFS）
深度优先搜索是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
#include <iostr
