关键点

• 无序区，一开始都是无序区
• 有序区，每次执行完有序区数量不断增大，无序区数量不断减小
• 排序的趟数

每趟遍历从无序区第二个元素开始向后找到最小的元素，和第一个元素交换，使得有序区数量增加1

趟数和每趟无序区下标都从1开始：
第1趟开始：有序区数量0，无序区数量n，无序区中选择最小值的下标：下标1,下标2,下标3...,下标n
第2趟开始：有序区数量1，无序区数量n-1，无序区中选择最小值的下标： 下标2,下标3,下标4...,下标n
第3趟开始：有序区数量2，无序区数量n-2，无序区中选择最小值的下标： 下标3,下标4,下标5...,下标n
第4趟开始：有序区数量3，无序区数量n-3，无序区中选择最小值的下标： 下标4,下标5,下标6...,下标n
第 i 趟开始：有序区数量 i-1，无序区数量 n-(i-1)=n-i+1，无序区中选择最小值的下标：下标i,下标i+1,...,下标n

下标一般都是从0开始，趟数和每趟无序区下标都转换成从0开始：
第0趟开始：有序区数量0，无序区数量n，无序区中选择最小值的下标：下标0,下标1,下标2...,下标n-1
第1趟开始：有序区数量1，无序区数量n-1，无序区中选择最小值的下标： 下标1,下标2,下标3...,下标n-1
第2趟开始：有序区数量2，无序区数量n-2，无序区中选择最小值的下标： 下标2,下标3,下标4...,下标n-1
第3趟开始：有序区数量3，无序区数量n-3，无序区中选择最小值的下标： 下标3,下标4,下标5...,下标n-1
第 i 趟开始：有序区数量 i，无序区数量 n-i，无序区中选择最小值的下标： 下标i,下标i+1,...,下标n-1

代码实现

#时间复杂度O(n^2)
def select_sort(li):
    n = len(li)
    for i in range(n-1):#n个数，n-1趟
        min_pos = i #记录无序区最小值的位置，即无序区的第一个元素
        for j in range(i+1,n):#第i趟时，无序区范围：下标i,下标i+1,...,下标n-1，从无序区范围的第二个开始一直到最后一个，即i+1~n-1，即range(i+1,n)
            if li[j] < li[min_pos]:
                min_pos = j
        li[i], li[min_pos] = li[min_pos], li[i]

排序稳定性

源数据中相同的元素相对顺序保持不变，即稳定排序
3 3 1 5使用选择排序就是不稳定，第一个1和第二个1排序完相对顺序变了。冒泡是稳定排序。
挨个换的是稳定排序，不挨个换的是不稳定排序