选择排序 (Selection Sort)

不断选择最小（或最大）元素放到已排序序列的末尾

算法原理

选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

核心思想：
  • 将数组分为"已排序区间"和"未排序区间"。
  • 每次从未排序区间中找到最小值，将其与未排序区间的第一个元素交换。
  • 已排序区间逐步扩大，直到覆盖整个数组。

演示

点击"开始排序"以观察算法执行过程
for (int i = 0; i < n - 1; i++) {
int min_idx = i; // 假设当前 i 是最小
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j; // 更新最小值下标
}
}
swap(arr[i], arr[min_idx]); // 交换
}

算法分析

特性 描述
时间复杂度 O(n²) - 无论什么数据，都是 O(n²)
空间复杂度 O(1) - 只需要常数级的额外空间
稳定性 不稳定 -例如 [5, 8, 5, 2] 第一遍扫描及交换会破坏 5 的相对顺序