选择排序（Selection Sort）

原理

• 不断从未排序部分中寻找最小（大）值
• 然后与未排序部分的第一项交换位置
• （前两项循环）
• 直到所有项均已排序
  
  

这样说的可能有点难懂，结合动画来看一下

*橙色部分为已排序部分，红色为未排序中的最小值*

*与最小值交换就是正排序，最大值就是倒排序*

还不懂吗？再来个图看看（倒排序）

用python实现

我们要功克的四个问题：

• 1.实现重复不断的过程
• 2.确定未排序部分的范围
• 3.寻找列表中的最大值
• 4.给列表中的元素交换位置

1

所以，列表中的元素个数为len(lst),
循环（len(lst)-1)次，
排好(len(lst)-1)个元素

for r in range(len(lst)-1):
    # 确定未排序部分范围

2

假设有一个列表lst：[9, 15, 3, 11, 6]，他们对应的索引分别是是 ：0 1 2 3 4

第1次循环：未排序部分0~4 r：0
第2次循环：未排序部分1~4 r：1
第3次循环：未排序部分2~4 r： 2
第4次循环：未排序部分3~4 r: 3

由此得出，未排序部分的第一项：lst[r]，未排序部分：range(r, len(lst))

for i in range(r, len(lst)):

3、4

这儿不说了，大家理解着注释看一下完整代码

lst = [9, 15, 3, 11, 6]
for r in range(len(lst) - 1):
    # 定义一个变量max_i,记录当前最大值的索引
    # max_i初始值为待排序列表的第一个索引：r
    max_i = r
    # 在未排序部分寻找最大值
    for i in range(r + 1, len(lst)):
        if lst[i] > lst[max_i]:
            max_i = i
    # 找到最大值后与未排序部分的第一项交换位置
    lst[max_i], lst[r] = lst[r], lst[max_i]
print(lst)