26考研——排序_选择排序_选择排序的基本思想 简单选择排序（8）

408答疑

---

---

四、选择排序

选择排序的基本思想

• 每一趟（如第 $i$ 趟）在剩下 $n-i+1$（$i=1,2,\dots ,n-1$）个待排序元素中选取关键字最小的元素，作为有序子序列的第 $i$ 个元素，直到第 $n-1$ 趟做完，待排序元素只剩下 1 个，就不用再选。选择排序中的堆排序是历年统考考查的重点。

简单选择排序

定义

选择排序是一种简单直观的排序算法。顾名思义，每次通过选择剩下元素的极值（最大值或最小值），往已排序好的序列之后存放，通过选择元素而达到的排序。

算法思想

• 假设排序表为 $L[\mathrm{1..}n]$，第 $i$ 趟排序即从 $L[i..n]$ 中选择关键字最小的元素与 $L(i)$ 交换。
• 每一趟排序可以确定一个元素的最终位置，这样经过 $n-1$ 趟排序就可使整个排序表有序。

性能分析

空间效率

• 空间效率为 $O(1)$，仅使用常数个辅助单元。

时间效率

• 元素移动的操作次数很少，不会超过 $3(n-1)$ 次，最好的情况是移动 0 次，此时对应的表已经有序。
• 元素间比较的次数与序列的初始状态无关，始终是 $n(n-1)/2$ 次，因此时间复杂度始终是 $O(n^2)$。

稳定性

• 简单选择排序是一种不稳定的排序算法。
• 在第 $i$ 趟找到最小元素后，和第 $i$ 个元素交换，可能会导致第 $i$ 个元素与含有相同关键字的元素的相对位置发生改变。
• 例如，表 L = { 2 1 , 2 2 , 1 } L = \{2_1, 2_2, 1\} L={21​,22​,1}，经过一趟排序后 L = { 1 , 2 2 , 2 1 } L = \{1, 2_2, 2_1\} L={1,22​,21​}，最终排序序列也是 L = { 1 , 2 2 , 2 1 } L = \{1, 2_2, 2_1\} L={1,22​,21​}，显然，$2_1$ 与 $2_2$ 的相对次序已发生变化。

适用性

• 简单选择排序适用于顺序存储和链式存储的线性表，以及关键字较少的情况。

九、参考资料

鲍鱼科技课件

b站免费王道课后题讲解:

网课全程班:

26王道考研书