Python|Python 排序算法之选择排序(5/8)
思想:
【Python|Python 排序算法之选择排序(5/8)】列表最前面有一个假想的空表,我们从未经排序的部分取出最小的值,然后依次放入这个假想的空表,最后完成排序。
慢动作解释:
5 6 1 2 9, m = 0
首先假定第一个数是最小值。然后记录它的位置为 m。
然后依次后后面的数比较。比如 5 和 6 比,5 仍然是最小,继续推进。
5 和 1 比较, 1 更小,那么更新 m 的值为 1 的位置。
5 6 1 2 9, m = 2
然后继续跑完剩下的,m 始终不变,可以确定 1 是最小的。因此进行数字 5 和数字 1 的交换。同时外层 for 推进,由于可以确定首位是最小值,因此 m 从 1 开始。
1 6 5 2 9, m = 1
6 和 5 比较,5 更小,因此:
1 6 5 2 9, m = 5
2 又比 5 小,因此:
1 6 5 2 9, m = 3
然后交换 lst[m] 和 lst[1],由于确定最前面两个是最小值,因此 m 从 2 开始:
1 2 5 6 9, m = 2
5 和 6、9比较,没有变化。
1 2 5 6 9, m = 3
1 2 5 6 9, m = 4
结束。
代码实现
def selection_sort(lst):
n = len(lst)
for i in range(n-1): # 不用循环到 n,因为最后一项肯定是最大的。
m = i # 暂定的最小数的位置
for j in range(i+1, n):
if lst[j] < lst[m]:
m = j# 新的最小数的位置
lst[m], lst[i] = lst[i], lst[m]
print(lst)
return lst
记忆结构: for for if。其中最后一个 for 是 lst[j] 和 lst[m] (最小值)比较,而不是和 lst[i],切记。动画展示 http://v.youku.com/v_show/id_XNTM1NTQzMDYw.html
推荐阅读
- python学习之|python学习之 实现QQ自动发送消息
- 画解算法(1.|画解算法:1. 两数之和)
- 逻辑回归的理解与python示例
- Guava|Guava RateLimiter与限流算法
- python自定义封装带颜色的logging模块
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- Python基础|Python基础 - 练习1
- Python爬虫|Python爬虫 --- 1.4 正则表达式(re库)
- 一个选择排序算法
- Python(pathlib模块)