选择排序

选择排序和插入排序类似，也是将数组分成了未排序部分和已排序部分，每一次循环的都在未排序的区间里面找到最小或者最大的值，然后将其放在左边已排序区间。

代码实现

"""
    选择排序
    Author: xingrui
"""


# 选择排序 - 正序
def selectSortWithAsc(nums: list) -> list:
    length = len(nums)

    for i in range(0, length - 1):
        minIndex = i

        for j in range(i + 1, length):
            if nums[minIndex] > nums[j]:
                minIndex = j

        if minIndex != i:
            temp = nums[i]
            nums[i] = nums[minIndex]
            nums[minIndex] = temp

    return nums


# 选择排序 - 逆序
def selectSortWithDesc(nums: list) -> list:
    length = len(nums)

    for i in range(0, length - 1):
        maxIndex = i

        for j in range(i + 1, length):
            if nums[maxIndex] < nums[j]:
                maxIndex = j

        if maxIndex != i:
            temp = nums[i]
            nums[i] = nums[maxIndex]
            nums[maxIndex] = temp

    return nums


if __name__ == "__main__":
    nums = [4, 5, 2, 6, 2, 3, 9, 3]

    selectSortWithAsc(nums)
    print('插入排序，正序排列', nums)

    selectSortWithDesc(nums)
    print('插入排序，逆序排列', nums)

分析

选择排序的最好最坏时间复杂度都是，空间复杂度为。值得注意的是，冒泡排序和插入排序都是稳定的排序算法（即数组当中相同的元素在排序之后，前后顺序保持不变），而选择排序不是稳定的排序算法，举个例子，有如下数组

按照选择排序的原理，会找到未排序区间里最小的元素，1。然后将1放到最左边，所以要将原本在最左边的元素5与1进行交换，这样一来，原本在最前面的5跑到了最后，数组当中两个5的相对关系发生了变化，所以选择排序不是稳定的排序算法。

参考

https://www.jianshu.com/writer#/notebooks/44679128/notes/66785923/preview
https://time.geekbang.org/column/article/41802
https://www.jianshu.com/p/135261a2f8d1
https://www.jianshu.com/p/05cdb2735d3b