从新手到高手！C++ 实现快速排序和 Floyd-Warshall 算法（含完整代码解析）

引言

算法是编程中不可或缺的核心技能，而快速排序和 Floyd-Warshall 算法则是两个具有代表性的经典算法。快速排序是处理大规模数据的高效排序算法，而 Floyd-Warshall 是解决图中 任意两点之间最短路径问题 的动态规划算法。本篇文章将通过 C++ 实现这些算法，带你深入理解它们的原理和实际应用。

第一部分：快速排序（Quick Sort）

1.1 算法简介

快速排序（Quick Sort）是一种基于分治思想的高效排序算法，平均时间复杂度为 O(nlog⁡n)O(nlogn)，而最坏情况下时间复杂度为 O(n2)O(n2)。它的核心在于每次选择一个“基准”元素（pivot），然后通过分区操作将数组分为小于基准和大于基准的两部分，并递归地对这两部分进行排序。

1.2 算法步骤

选择数组中的一个元素作为 基准值（pivot）。
将数组分成两部分：一部分的元素小于基准值，另一部分的元素大于基准值。
对两部分递归进行快速排序。

1.3 代码实现

#include <iostream>
#include <vector>
using namespace std;// 快速排序的分区函数
int partition(vector<int>& arr, int low, int high) {int pivot = arr[high]; // 选择最后一个元素作为基准int i = low - 1;       // i 是较小元素的索引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(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() {vector<int> arr = {10, 7, 8, 9, 1, 5};int n = arr.size();cout << "排序前的数组: ";for (int num : arr) cout << num << " ";cout << endl;quickSort(arr, 0, n - 1);cout << "排序后的数组: ";for (int num : arr) cout << num << " ";cout << endl;return 0;
}

1.4 执行结果

排序前的数组: 10 7 8 9 1 5
排序后的数组: 1 5 7 8 9 10

1.5 算法特点

时间复杂度：
- 最优情况：O(nlog⁡n)O(nlogn)（每次分区将数组均分为两半）。
- 最坏情况：O(n2)O(n2)（当数组已经有序或所有元素相同时，分区效果较差）。
空间复杂度：O(log⁡n)O(logn)（递归调用栈所需的额外空间）。
适用场景：适合处理大规模数据且分区效果较好的情况。

第二部分：Floyd-Warshall 算法

2.1 算法简介

Floyd-Warshall 是一种解决任意两点之间最短路径问题的算法，其核心思想是通过动态规划的方法，不断更新起点与终点之间的最短路径。它适用于 加权有向图，并且可以处理图中带负边的情况，但前提是图中不能有负权回路。

2.2 算法步骤

初始化一个二维数组 dist，其中 dist[i][j] 表示从节点 i 到节点 j 的路径权重。如果 i == j，dist[i][j] = 0；如果节点 i 和节点 j 之间有边，则设置为边的权重，否则设为无穷大。
对于每个中间节点 k，依次尝试优化从 i 到 j 的路径长度：
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。
重复以上过程，直到所有节点之间的最短路径计算完成。

2.3 代码实现

#include <iostream>
#include <vector>
using namespace std;const int INF = 1e9; // 用于表示无穷大void floydWarshall(vector<vector<int>>& graph) {int n = graph.size();vector<vector<int>> dist = graph; // 距离矩阵初始化为图的权重矩阵for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (dist[i][k] != INF && dist[k][j] != INF) {dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);}}}}// 输出最终的最短路径矩阵cout << "最短路径矩阵: " << endl;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (dist[i][j] == INF) {cout << "INF ";} else {cout << dist[i][j] << " ";}}cout << endl;}
}int main() {vector<vector<int>> graph = {{0, 3, INF, 7},{8, 0, 2, INF},{5, INF, 0, 1},{2, INF, INF, 0}};floydWarshall(graph);return 0;
}

2.4 执行结果

输入图的邻接矩阵为：

0   3   INF 7
8   0   2   INF
5   INF 0   1
2   INF INF 0

执行 Floyd-Warshall 算法后，输出的最短路径矩阵为：

0   3   5   6
7   0   2   3
3   6   0   1
2   5   7   0

2.5 算法特点

时间复杂度：O(n3)O(n3)（三重循环遍历所有节点对）。
空间复杂度：O(n2)O(n2)（存储距离矩阵所需的空间）。
适用场景：适用于密集图或需要计算所有节点对之间的最短路径的情况。

第三部分：快速排序与 Floyd-Warshall 的结合与对比

3.1 不同的适用场景

快速排序：适合需要对大规模数据进行排序的情况，是集合管理的基础操作。
Floyd-Warshall：适合密集图中任意两点间最短路径的计算，尤其是需要同时考虑多对节点路径的情况。

3.2 时间复杂度的差异

快速排序的平均时间复杂度为 O(nlog⁡n)O(nlogn)，最坏情况为 O(n2)O(n2)。
Floyd-Warshall 的时间复杂度为 O(n3)O(n3)，适用于节点数较少的密集图。