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

选择排序

一、核心原理

每一轮从未排序区间找到最小值（或最大值），和未排序区间第一个元素交换；划分：已排序区间 | 未排序区间，逐步扩大左边有序区间。

二、算法复杂度

• 时间复杂度：最好 / 最坏 / 平均 O (n²)
• 空间复杂度：O(1)原地排序
• 不稳定排序

三、特点

1. 不依赖初始序列顺序，无论有序无序，都要走完固定比较次数；
2. 交换次数远少于冒泡排序，实际效率比冒泡略高；
3. 不稳定：如2, 2, 1排序后相对位置会变；
4. 简单直观，适合小规模数据。

四、不稳定举例

序列：2₁, 2₂, 1第一轮找到最小值 1，和第一位 2₁交换 →1,2₂,2₁两个 2 相对顺序改变 →不稳定

五、算法思路

1. 外层循环：控制未排序区间起始位置i
2. 内层循环：从i+1到末尾，找最小值下标
3. 把最小值下标元素 和i位置元素交换

C++ 源代码

1. 升序选择排序（标准版）

cpp

#include <iostream> #include <vector> using namespace std; // 选择排序 升序 void selectSort(vector<int>& 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() { vector<int> a = {5, 3, 8, 4, 2}; selectSort(a); for (int x : a) { cout << x << " "; } return 0; }

2. 降序版本（找最大值）

cpp

void selectSortDesc(vector<int>& 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]); } }