Python 算法教程（2）：选择排序详解
前言
选择排序（Selection Sort）是最简单的排序算法之一，虽然效率不高，但理解它有助于学习更高级的排序。
一、算法原理
核心思想
每次从未排序部分找到最小元素，放到已排序部分末尾。
动画演示
初始：[64, 25, 12, 22, 11]
第 1 轮：找到 11，交换 64→[11, 25, 12, 22, 64]
第 2 轮：找到 12，交换 25→[11, 12, 25, 22, 64]
第 3 轮：找到 22，交换 25→[11, 12, 22, 25, 64]
结果：[11, 12, 22, 25, 64]二、代码实现
基础版本
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr优化版本（减少交换）
def selection_sort_optimized(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
if min_idx != i: # 只在需要时交换
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr三、复杂度分析
| 情况 | 时间 | 空间 | 稳定性 |
|---|---|---|---|
| 最好 | O(n²) | O(1) | 不稳定 |
| 平均 | O(n²) | O(1) | 不稳定 |
| 最坏 | O(n²) | O(1) | 不稳定 |
四、与冒泡排序对比
对比项 冒泡排序 选择排序
比较次数 O(n²) O(n²)
交换次数 O(n²) O(n)
稳定性 稳定 不稳定
效率 较低 略高五、面试考点
- 时间复杂度？O(n²) 所有情况
- 稳定吗？不稳定
- 交换次数？最多 n-1 次
- 何时使用？教学、小规模数据
总结
选择排序简单易懂，但效率低，实际应用中建议使用快速排序或归并排序。
下一篇：插入排序
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
