选择排序算法（Python实现，图文并茂）

选择排序是一种简单直观的排序算法。它的工作原理是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，所以称为选择排序。

选择排序算法的基本思想：先从序列的未排序区域中选择一个最小的元素，把它与序列中的第 1 个元素交换位置；再从剩下的未排序区域中选出一个最小的元素，把它与序列中的第 2 个元素交换位置……如此反复操作，直到序列中的所有元素按升序排列完毕。

例如，对无序表 [56，12，80，92，20] 采用选择排序算法进行排序，具体过程如下：

1) 第一次遍历时，从下标为 1 的位置即 56 开始，找出关键字值最小的记录 12，同下标为 0 的关键字 56 交换位置。


2) 第二次遍历时，从下标为 2 的位置即 56 开始，找出最小值 20，同下标为 2 的关键字 56 互换位置。


3) 第三次遍历时，从下标为 3 的位置即 80 开始，找出最小值 56，同下标为 3 的关键字 80 互换位置。


4) 第四次遍历时，从下标为 4 的位置即 91 开始，找出最小值 80，同下标为 4 的关键字 92 互换位置。


5) 至此简单选择排序算法完成，无序列变为有序表。

【实例】　利用选择排序算法对序列 [56，12，80，92，20] 进行排序。

实现步骤如下：

• 步骤 1：找出序列中的最大值，然后跟最后一个元素交换位置。
• 步骤 2：循环执行步骤1。
• 步骤 3：优化函数并封装成函数。

# 步骤 1
lst = [56, 12, 80, 92, 20]
index = 0  # 定义一个存放最大值的索引值的变量，默认为 0
for i in range(len(lst) - 1):
    if lst[i + 1] > lst[index]:
        index = i + 1
# 结束完循环之后 index 为最大值的索引值
lst[index], lst[len(lst) - 1] = lst[len(lst) - 1], lst[index]
# 此时将最大值放到了列表最后
print(lst)
# [56, 12, 80, 20, 92]

# 步骤 2
lst = [56, 12, 80, 92, 20]
for i in range(len(lst) - 1):  # 定义一个存放最大值的索引值的变量，默认为 0
    index = 0
    for j in range(len(lst) - 1 - i):
        # 当循环第一次时，i = 0, 需要循环整个列表才能找出最大值
        # 当循环第二次时，i = 1, 不需要循环最后一个元素，因为最后一个元素一定是最大的
        # ...
        if lst[j + 1] > lst[index]:
            index = j + 1
    # 结束完循环之后 index 为最大值的索引值，将最大值放置参加循环的最后一位
    lst[index], lst[len(lst) - 1 - i] = lst[len(lst) - 1 - i], lst[index]
print(lst)
# [12, 20, 56, 80, 92]

# 步骤 3
def sort(lst):
    n = len(lst)
    for i in range(n - 1):
        index = 0
        for j in range(n - 1 - i):
            if lst[j + 1] > lst[index]:
                index = j + 1
        lst[index], lst[n - 1 - i] = lst[n - 1 - i], lst[index]
    return lst

lst = [56, 12, 80, 92, 20]
print(sort(lst))
# [12, 20, 56, 80, 92]