选择排序像整理书架一样学算法一、生活中的例子整理书架想象一下你的书架上有5本高低不同的书你想把它们**从矮到高**排好。**选择排序的思路**1. 先找出最矮的那本书把它放到第1位2. 在剩下的书里找出最矮的放到第2位3. 重复这个过程直到全部排好这就是**选择排序**——每轮选择剩余元素中的最小或最大值放到正确位置。---二、算法原理**核心思想**每轮从未排序部分找出最小值与未排序部分的第一个元素交换。**基本步骤**1. 第一轮在索引 0~n-1 中找最小值放到索引 02. 第二轮在索引 1~n-1 中找最小值放到索引 13. 重复 n-1 轮**动画演示**以 [5, 2, 4, 6, 1, 3] 为例初始[5, 2, 4, 6, 1, 3]第1轮找最小值1 → [1, 2, 4, 6, 5, 3]第2轮找最小值2 → [1, 2, 4, 6, 5, 3]第3轮找最小值3 → [1, 2, 3, 6, 5, 4]第4轮找最小值4 → [1, 2, 3, 4, 5, 6]第5轮找最小值5 → [1, 2, 3, 4, 5, 6]完成---三、代码实现Python基础版本pythondef selection_sort(arr):n len(arr)# 外层循环确定每轮起始位置for i in range(n - 1):# 假设当前位置的元素是最小值min_index i# 内层循环在未排序部分找真正的最小值for j in range(i 1, n):if arr[j] arr[min_index]:min_index j# 将最小值与当前位置交换arr[i], arr[min_index] arr[min_index], arr[i]# 打印每轮结果便于观察print(f第{i1}轮后{arr})return arr# 测试nums [5, 2, 4, 6, 1, 3]print(原始数组, nums)selection_sort(nums)**输出**原始数组 [5, 2, 4, 6, 1, 3]第1轮后[1, 2, 4, 6, 5, 3]第2轮后[1, 2, 4, 6, 5, 3]第3轮后[1, 2, 3, 6, 5, 4]第4轮后[1, 2, 3, 4, 5, 6]第5轮后[1, 2, 3, 4, 5, 6]降序排列找最大值pythondef selection_sort_desc(arr):n len(arr)for i in range(n - 1):max_index ifor j in range(i 1, n):if arr[j] arr[max_index]: # 改为找最大值max_index jarr[i], arr[max_index] arr[max_index], arr[i]return arr---四、复杂度分析| 情况 | 比较次数 | 交换次数 | 时间复杂度 ||------|---------|---------|-----------|| 最好 | n(n-1)/2 | 0 | O(n²) || 最坏 | n(n-1)/2 | n-1 | O(n²) || 平均 | n(n-1)/2 | n-1 | O(n²) |**空间复杂度**O(1)原地排序**特点**- ✅ 简单易懂容易实现- ✅ 交换次数最少最多 n-1 次- ❌ 时间复杂度高数据量大时慢- ❌ **不稳定排序**相同元素的相对位置可能改变---五、课堂活动设计活动1扑克牌排序游戏**材料**一副扑克牌只取数字牌1-10**步骤**1. 每组随机发5张牌2. 按照选择排序的思路手动排列3. 记录每轮找到的最小值和交换过程4. 小组比赛看谁最快排好活动2全班排队**场景**请10位同学上台每人胸前贴一个随机数字**过程**1. 第1位同学从第1~10位中找出数字最小的人交换位置2. 第2位同学从第2~10位中找最小交换位置3. 全班一起喊出每轮找到的最小值和交换过程活动3错误排查挑战python# 以下代码有错误请找出并改正def wrong_sort(arr):n len(arr)for i in range(n):min_index 0 # 错误1应该初始化为 ifor j in range(i, n):if arr[j] arr[min_index]:min_index jarr[i], arr[min_index] arr[min_index], arr[i]return arr**错误**1. min_index 0 应改为 min_index i2. 内层循环 range(i, n) 应改为 range(i1, n)---六、与其他排序算法对比| 排序算法 | 时间复杂度 | 稳定性 | 特点 ||---------|-----------|--------|------|| 选择排序 | O(n²) | ❌ 不稳定 | 交换次数少 || 冒泡排序 | O(n²) | ✅ 稳定 | 实现简单 || 插入排序 | O(n²) | ✅ 稳定 | 数据量小时快 || 快速排序 | O(n log n) | ❌ 不稳定 | 分治思想 || 归并排序 | O(n log n) | ✅ 稳定 | 需要额外空间 |**使用建议**- 数据量 1000选择排序可以接受- 数据量较大使用快速排序或归并排序- 几乎有序的数据插入排序更好---七、练习题基础题1. 手动模拟选择排序[8, 3, 7, 1, 5]2. 编写代码统计排序过程中的比较次数和交换次数### 进阶题1. 改进选择排序同时找出最大值和最小值减少循环次数2. 用选择排序对学生成绩进行排序结构体/对象3. 分析为什么选择排序是不稳定的请举例说明### 拓展思考- 如果数据是链表结构还能用选择排序吗- 能否用递归实现选择排序---八、总结口诀 **每轮找出最小数放到前面位置处。** **外圈循环 n-1 次内圈比较找索引。** **交换元素三步走简单排序学不愁。**选择排序是算法的hello world掌握了它就打开了排序算法的大门选择排序的基本概念选择排序是一种简单直观的排序算法适合用于教学场景。其核心思想是每次从未排序的部分中选择最小或最大的元素放到已排序部分的末尾。通过多次重复这一过程最终完成整个序列的排序。算法步骤初始化将整个序列分为已排序和未排序两部分初始时已排序部分为空。查找最小值从未排序部分中找到最小的元素。交换位置将找到的最小元素与未排序部分的第一个元素交换位置。更新边界将未排序部分的起始位置向后移动一位扩大已排序部分的范围。重复重复上述步骤直到未排序部分为空。示例代码Pythondef selection_sort(arr): n len(arr) for i in range(n): min_idx i for j in range(i1, n): if arr[j] arr[min_idx]: min_idx j arr[i], arr[min_idx] arr[min_idx], arr[i] return arr # 示例 arr [64, 25, 12, 22, 11] sorted_arr selection_sort(arr) print(排序后的数组:, sorted_arr)教学案例设计案例目标让学生理解选择排序的基本原理并能手动模拟排序过程。步骤准备一个简单的数字序列如[5, 3, 8, 6, 2]。在黑板上或屏幕上逐步展示每一轮排序的过程包括查找最小值和交换位置的操作。让学生分组模拟排序过程每组负责一轮排序最后汇总结果。时间复杂度分析选择排序的时间复杂度为 $O(n^2)$其中 $n$ 是序列的长度。这是因为算法需要进行 $n$ 轮查找每轮查找的范围逐渐缩小但总的比较次数为 $\frac{n(n-1)}{2}$。实际应用与局限性选择排序适合小规模数据的排序因为其实现简单且易于理解。但对于大规模数据其效率较低通常不推荐使用。教学中可以通过与其他排序算法如冒泡排序、快速排序对比帮助学生理解不同算法的优缺点。
