python算法之最low三人组之一——————选择排序

之前讲过了冒泡排序，我们再聊一聊最low三人组中的选择排序，选择排序的基本思想是：遍历整个序列，选取其中一个最小的数取出来，然后再次遍历除了刚刚选出来的最小的数的序列中最小的数

现在让我们看看代码实现

import random
def select_sort(li):
    new_li=[]
    for i in range(len(li)-1):    #第几趟遍历序列
        min_m=min(li)
        new_li.append(min_m)
        li.remove(min_m)
        print(new_li)
    print(new_li)
li=[random.randint(1,100) for i in range(10)]
print (li)
select_sort(li)

定义一个空的序列new_li来接受从li序列里面选到的最小的数，利用append内置函数将其加入新序列，再用remove内置函数删除原序列中的最小数，并在循环里加入print函数，看循环每一步的变化。

但是！！！！！我们写程序时应该注意时间复杂度和空间复杂度，正常情况下，时间复杂度最先考虑，在这个代码中明面上的时间复杂度为n，因为有一层循环，但是内层函数min()也是有n的时间复杂度，所以是n^2的时间复杂度。而且空间复杂度也有两倍的序列长度，那我们怎么办，才能解决呢。

进阶的方法在此！！！！

        我们换个思想，不建立新的列表来接受数，我们就把最小的数放到序列最前面，然后循环后面的序列即可，这样空间复杂度解决了，那时间复杂度我们看看代码

def select_sort(li):
    for i in range(len(li)-1):
        min_li=i
        for j in range(i+1,len(li)):
            if li[j]<li[min_li]:
                min_li=j
        li[i],li[min_li]=li[min_li],li[i]
    print(li)

新代码的思想为：用min_li来记录最小数的下标，最开始赋值为第一个数的下标，第一层循环为第几趟，第二层循环为取出循环中最小的数的下标，循环开始 为i+1，因为不需要和自己比较，所以不是从i开始，内层循环第i+1个数与下标为min_li的数比较，如果j小则赋值j给min_li，一次循环结束以后，交换最小的数到最前面则解决了时间复杂度的问腿，新代码的时间复杂度为o(n)。