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

    推荐阅读