1、简介

一趟遍历记录最小的数，放到第一个位置，再一趟遍历记录剩余列表中最小的数，继续放置…
问题是：怎么选出最小的数呐？

2、选择排序思路图

选择排序：固定一个位置，存放最大/最小的值，说白了，有序区是在第一个位置开始，最后一个位置结束。
选择排序升序的列表如下：
image.png
第一趟：此次循环对此比较交换，固定 第0个位置，然后依次跟后面比较，得出有序区最小值 [2]。
image.png
第二趟：此次循环对此比较交换，固定 第1个位置，然后依次跟后面比较，得出有序区最小值 [2,6]。
image.png

第三趟：此次循环对此比较交换，固定 第2个位置，然后依次跟后面比较，得出有序区最小值 [2,6,7]。
image.png

第四趟：此次循环对此比较交换，固定 第3个位置，然后依次跟后面比较，得出有序区最小值 [2,6,7,8,9]。
image.png
最后一个9不需要固定了，因为最后一个不需要再比较了。所以5个数，一共比较了 4 趟，每趟 比较次数 是(i+1,5)。
所以按变量来算的话，外层的趟数：len(li)-1，里面的比较趟数(i+1,len(li))

3、选择排序实现

3.1、选择排序

根据上面的逻辑图的思路，我们接下来 实现 选择排序的代码，代码如下：

  1. def select_sort(li):
  2.     for i in range(len(li)-1):   #一共走了 len(li)-1趟，因为最后一个数不需要比较
  3.         min_loc = i    #固定最小值的位置
  4.         for j in range(i+1,len(li)):   #每一趟经过 i+1,len(li)比较
  5.             if li[j] < li[min_loc]:   #进行比较
  6.                 min_loc = j   #固定最小值的位置下标值互换
  7.         if min_loc != i:   #这段代码可以不要
  8.             li[i],li[min_loc] = li[min_loc],li[i]   #互换值

时间复杂度：O(n²)