1.4 选择排序

[utterances-bot]

1.4 选择排序

选择排序 # 1. 选择排序算法思想 # 选择排序（Selection Sort）基本思想： 将序列分为两部分：前边 i - 1 个元素为已排序部分，后边 n - i + 1

https://algo.itcharge.cn/01_array/01_04_array_selection_sort/

[Is-Grit]

牛，就是感觉跟冒泡其实时间复杂度差不多，为啥不直接用冒泡呢。。。

[EnjianGong]

冒泡排序每轮交换的次数比较多，而选择排序每轮只交换一次；在时间效率上，选择排序优于冒泡排序。

[hanxiang0227]

打卡

[Wan-Yifei]

虽然元素交换次数显著降低，但是却需要频繁更新最小值的索引。但是操作一个值应该是比交换两个值开销要小的。

[Jiurouqiu8]

def sel(lst):
    for i in range(len(lst)-1):

        temp_min = i

        for j in range(i+1,len(lst)):
            if lst[j] < lst[i]:
                temp_min = j
                if i != temp_min:
                    temp = lst[i]
                    lst[i] = lst[j]
                    lst[j] = temp
    return lst
lst = [5,2,3,6,1,4]
print(sel(lst))

[liguohan]

这篇文章动画演示更好理解：https://mp.weixin.qq.com/s/iJvPegXpBRI6dkzLWEE6dA

[Wan-Yifei]

感觉每轮遍历都直接用min()检查剩下的数组也行啊，然后把最小值移动到第二位。这样可以避免手动写比较。

[Xielby]

那就要把最小值从后边的数组删掉，然后把最小值放入已排序的末尾，然后把已排序末尾的值（未排序首位的值）放入未排序数组，也就是说min无法获得最小值的下标不好操作，如果用查找函数找下标有点画蛇添足了；而且min函数用到切片了吧，相当于创建新数组了，空间复杂度就不是1了，

[Xielby]

看完1.2-1.4我有一个问题就是，使用冒泡和选择排序后，原数组已经被覆盖了，新数组相同值，已经没有排序前的记号（下标）了，那这里所说的排序稳定性还有意义吗，值都是相同的？可能如果是比较字符串，给字典内的值排序什么的有别的值有意义？