选择排序：原理、特点与实现详解

选择排序一、核心原理每一轮从未排序区间找到最小值或最大值和未排序区间第一个元素交换划分已排序区间 | 未排序区间逐步扩大左边有序区间。二、算法复杂度时间复杂度最好 / 最坏 / 平均 O (n²)空间复杂度O(1)原地排序不稳定排序三、特点不依赖初始序列顺序无论有序无序都要走完固定比较次数交换次数远少于冒泡排序实际效率比冒泡略高不稳定如2, 2, 1排序后相对位置会变简单直观适合小规模数据。四、不稳定举例序列2₁, 2₂, 1第一轮找到最小值 1和第一位 2₁交换 →1,2₂,2₁两个 2 相对顺序改变 →不稳定五、算法思路外层循环控制未排序区间起始位置i内层循环从i1到末尾找最小值下标把最小值下标元素 和i位置元素交换C 源代码1. 升序选择排序标准版cpp#include iostream #include vector using namespace std; // 选择排序 升序 void selectSort(vectorint arr) { int n arr.size(); for (int i 0; i n - 1; i) { // 假设i位置是最小值下标 int minIndex i; // 遍历后面无序区间找真正最小值下标 for (int j i 1; j n; j) { if (arr[j] arr[minIndex]) { minIndex j; } } // 交换最小值到无序区间首位 swap(arr[i], arr[minIndex]); } } int main() { vectorint a {5, 3, 8, 4, 2}; selectSort(a); for (int x : a) { cout x ; } return 0; }2. 降序版本找最大值cppvoid selectSortDesc(vectorint arr) { int n arr.size(); for (int i 0; i n - 1; i) { int maxIndex i; for (int j i 1; j n; j) { if (arr[j] arr[maxIndex]) maxIndex j; } swap(arr[i], arr[maxIndex]); } }