C++选择排序详解（从零开始掌握选择排序算法）

选择排序的工作原理

假设我们有一个数组：[64, 25, 12, 22, 11]。选择排序会按以下步骤进行：

1. 在整段数组中找到最小值（11），与第一个元素（64）交换 → [11, 25, 12, 22, 64]
2. 在剩余未排序部分（从索引1开始）找最小值（12），与第二个元素（25）交换 → [11, 12, 25, 22, 64]
3. 继续此过程，直到整个数组有序。

C++ 实现选择排序

下面是一个完整的 C++选择排序 实现代码：

#include <iostream>#include <vector>using namespace std;void selectionSort(vector<int>& arr) {    int n = arr.size();        // 遍历数组的每一个位置    for (int i = 0; i < n - 1; i++) {        int minIndex = i; // 假设当前位置是最小值                // 在未排序部分寻找真正的最小值        for (int j = i + 1; j < n; j++) {            if (arr[j] < arr[minIndex]) {                minIndex = j;            }        }                // 交换最小值到已排序部分的末尾        if (minIndex != i) {            swap(arr[i], arr[minIndex]);        }    }}int main() {    vector<int> arr = {64, 25, 12, 22, 11};        cout << "排序前: ";    for (int x : arr) {        cout << x << " ";    }    cout << endl;        selectionSort(arr);        cout << "排序后: ";    for (int x : arr) {        cout << x << " ";    }    cout << endl;        return 0;}

算法复杂度分析

• 时间复杂度：无论最好、最坏还是平均情况，都是 O(n²)，因为需要两层嵌套循环。
• 空间复杂度：O(1)，属于原地排序算法，只需要常数级别的额外空间。
• 稳定性：不稳定。例如，如果数组中有相同元素，它们的相对位置可能在排序过程中被改变。

适用场景

虽然 选择排序算法 的效率不如快速排序或归并排序，但由于其实现简单、代码量少，非常适合教学和小规模数据排序。如果你正在学习 C++ 基础，这是一个绝佳的入门练习。

总结

通过本篇 C++排序教程，你应该已经掌握了选择排序的基本原理和实现方法。记住，理解算法比死记硬背更重要。建议你自己动手编写代码，并尝试对不同数据进行测试，加深理解。

关键词回顾：C++选择排序、选择排序算法、C++排序教程、简单排序算法。