使用C++实现多个经典算法

在计算机科学中，算法是解决问题的核心。无论是排序、搜索、还是图论问题，掌握和理解各种算法对于编程能力的提升至关重要。本文将通过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