简单选择排序 · 融合风（象牙 + Obsidian 入口）

速查

简单选择排序是最基本的选择排序：每趟从未排序部分选最小元素与未排序部分首个元素交换，共 $n-1$ 趟。比较次数始终 $\frac{n(n-1)}{2}$（与初始序列无关），交换最多 $n-1$ 次，不稳定。

核心概念 ▾

简单选择排序将数组分为已排序和未排序两部分，每趟从未排序部分中选出最小元素，与未排序部分的第一个元素交换。

核心思想：每趟确定一个最小元素的最终位置，共 $n-1$ 趟。

项目	值
最好时间	$O(n^2)$
最坏时间	$O(n^2)$
平均时间	$O(n^2)$
空间	$O(1)$
稳定性	❌ 不稳定
比较次数	与初始序列无关，始终 $\frac{n(n-1)}{2}$
交换次数	最多 $n-1$ 次

算法步骤 ▾

在 $A[i..n]$ 中找到最小元素 $A[min]$
将 $A[min]$ 与 $A[i]$ 交换
重复以上步骤，$i$ 从 1 到 $n-1$

void SelectSort(int A[], int n) {
    int i, j, min;
    for (i = 1; i < n; i++) {        // 共 n-1 趟
        min = i;
        for (j = i+1; j <= n; j++)  // 在未排序部分找最小
            if (A[j] < A[min]) min = j;
        if (min != i) swap(A[i], A[min]);
    }
}

手算示例 ▾

对 49, 38, 65, 97, 76, 13, 27, 49* 排序：

初始:  49 38 65 97 76 13 27 49*
第1趟: 找到最小13，与49交换
  [13] 38 65 97 76 49 27 49*
第2趟: 在38,65,97,76,49,27,49*中找最小27，与38交换
  [13 27] 65 97 76 49 38 49*
第3趟: 最小38，与65交换
  [13 27 38] 97 76 49 65 49*
第4趟: 最小49，与97交换
  [13 27 38 49] 76 97 65 49*
第5趟: 最小49*，与76交换
  [13 27 38 49 49*] 97 65 76
第6趟: 最小65，与97交换
  [13 27 38 49 49* 65] 76 97
第7趟: 最小76，已在正确位置
  [13 27 38 49 49* 65 76 97]

关键性质 ▾

性质	说明
比较次数	始终 $\frac{n(n-1)}{2}$，与初始序列无关
交换次数	最多 $n-1$ 次
时间	$O(n^2)$（最好 / 平均 / 最坏）
空间	$O(1)$
稳定性	❌ 不稳定

不稳定的原因

例：[5, 5*, 3]：第 1 趟找到最小 3，与第 1 个 5 交换 → [3, 5*, 5]，5 和 5* 的相对位置改变了。

易错点 ▾

注意

比较次数始终为 $\frac{n(n-1)}{2}$，与初始序列无关（区别于冒泡排序）
不稳定！交换可能改变相等元素相对位置
每趟只交换一次（或 0 次），不像冒泡可能多次交换
每趟确定的是最小值放到前面（不是最大值）

核心结论 ▾

必背时间 $O(n^2)$；比较次数 $\frac{n(n-1)}{2}$ 与初始序列无关；交换 $\leq n-1$ 次；不稳定；堆排序是其改进（用堆 $O(\log n)$ 找最小）；原地排序空间 $O(1)$。

记忆卡片 ▾

比较次数？

始终 $\frac{n(n-1)}{2}$，与初始序列无关。

稳定吗？

不稳定。交换可能改变相等元素相对位置。

与冒泡相比的优势？

交换次数少，最多 $n-1$ 次（冒泡最坏 $n(n-1)/2$）。

每趟确定什么？

未排序部分最小元素的最终位置。

交互动画 · 简单选择排序逐趟 ▾

点击「下一趟」执行一次查找最小 + 交换

核心概念 ▾

算法步骤 ▾

手算示例 ▾

关键性质 ▾

不稳定的原因

易错点 ▾

核心结论 ▾

记忆卡片 ▾

交互动画 · 简单选择排序逐趟 ▾

相关知识点