冒泡排序
工作原理
冒泡排序通过重复遍历数组，将相邻的元素进行比较并交换，使得最大的元素逐渐“冒泡”到数组的末尾。每完成一趟排序，最大的元素就会被固定在最后。
实现细节：
- 外层循环控制排序趟数，从第一个元素开始到最后一个元素。
- 内层循环进行相邻元素比较，从第一个元素到未排序部分的最后一个元素。
- 交换相邻元素的顺序以确保较大的元素在后面。
#include <vector>
using namespace std;void Bubblesort(vector<int> &v) {int len = v.size();for (int i = 0; i < len; i++) {for (int j = 0; j < len - 1 - i; j++) {if (v[j] > v[j + 1]) { // 从小到大排序swap(v[j], v[j + 1]); // 交换}}}
}
时间复杂度：
- 最坏情况（逆序）：O(n²)
- 最好情况（已排序）：O(n)
- 平均情况：O(n²)
空间复杂度：O(1)
优缺点：
- 优点：简单易懂，容易实现，适合教学。
- 缺点：效率低下，尤其对于大规模数据不适用。
应用实例：可以用于对小数组的排序，比如少量成绩的排序。
选择排序
工作原理
选择排序的思路是将数组分为已排序部分和未排序部分。在每一趟中，从未排序部分找到最小的元素，并将其放到已排序部分的末尾。
实现细节：
- 外层循环遍历整个数组，控制已排序部分的末尾。
- 内层循环找到当前未排序部分的最小元素。
- 交换最小元素与未排序部分的开头。
#include <vector>
using namespace std;void Choicesort(vector<int> &v) {int len = v.size();for (int i = 0; i < len - 1; i++) {int min_index = i; // 假设当前下标的元素为最小值for (int j = i + 1; j < len; j++) {if (v[j] < v[min_index]) { // 更新最小值的索引min_index = j;}}swap(v[min_index], v[i]); // 交换}
}
时间复杂度：
- 无论是最佳、最坏还是平均情况：O(n²)
空间复杂度：O(1)
优缺点：
- 优点：简单，交换次数较少（较少交换操作）。
- 缺点：效率低，尤其是在数组较大时，适用性差。
应用实例：可以用于手动选择最小值并放置，适合小规模数据处理。
插入排序
工作原理
插入排序的核心思想是将每个元素插入到已排序的部分中。每次处理一个元素时，将其与已排序部分的元素进行比较，找到合适的位置进行插入。
实现细节：
- 外层循环从第二个元素开始遍历（第一个元素默认已排序）。
- 内层循环从当前元素开始向前遍历，寻找插入位置。
- 将大于当前元素的元素向后移动，为当前元素腾出位置。
#include <vector>
using namespace std;void InsertSort(vector<int> &v) {int len = v.size();for (int i = 1; i < len; ++i) {int temp = v[i]; // 当前待插入的元素int j = i - 1;while (j >= 0 && v[j] > temp) { // 移动已排序部分元素v[j + 1] = v[j];j--;}v[j + 1] = temp; // 插入元素到合适的位置}
}
时间复杂度：
- 最坏情况（逆序）：O(n²)
- 最好情况（已排序）：O(n)
- 平均情况：O(n²)
空间复杂度：O(1)
优缺点：
- 优点：对小规模或部分有序数据效率高；稳定性好（相同元素顺序不变）。
- 缺点：对于大规模数据表现不佳。
应用实例：适合实时插入数据的场景，例如实时数据流处理、牌局排序等。
适用场景总结
| 排序算法 | 最佳适用场景 | 不适用场景 |
|---|---|---|
| 冒泡排序 | 学习排序概念，处理少量数据 | 大数据量排序，性能要求高的场景 |
| 选择排序 | 数据量小且不要求稳定性时 | 大数据量排序 |
| 插入排序 | 小规模或部分有序数据排序，实时数据处理 | 大数据量，完全无序的数据 |