【Python排序算法系列】—— 选择排序

选择排序

过程演示：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

选择排序对冒泡排序进行了改进，保留了其基本的多趟比对思路，每趟都使当前最小项就位。
但选择排序对交换进行了削减，相比起冒泡排序进行多次交换，每趟仅进行1次交换，记录最小项的所在位置，最后再跟本趟第一项交换  ---> 两两对比，小（大）的放前（后）面，对比过程不发生交换。

选择排序的时间复杂度比冒泡排序稍优but

比对次数不变，还是0(n²)，

而交换次数则减少为0(n)。

选择排序实现代码：

#默认第一个是最小，然后与后面进行比较，遇到最小就交换，不影响比较过程。
def selectionSort(arr):
    # i : 记录当前位置的索引
    for i in range(len(arr)):
        #初始化变量positionMin 为 i， 记录最小元素的索引位置
        positionofMin = i #默认最小值的下标从0开始
        # j ：记录后面待比较元素的位置索引
        for j in range(i + 1,len(arr)):
            #对比找到最小值，然后更新最小值下标
            if arr[positionofMin] > arr[j]:
                positionofMin = j
        #将最小元素 放到 已排好序部分的末尾
        arr[i],arr[positionofMin] = arr[positionofMin],arr[i]
    return arr
list = [5,3,1,4,2]
print(selectionSort(list))

分析选择排序：

选择排序算法和冒泡排序算法的比较次数相同，所以时间复杂度也是 O(n²)。但是，由于减少了交换次数，因此选择排序算法通常更快。

Practice2：

选择排序可以先排小的再排大的，也可以逆过来先排大的再排小的。

👇下面是我的解题思路：

这道题，我们可以一眼看出它是先排大的数再排小的数，因为如果先排小的数，应该是先排1，很明显没有这个选项。

所以，我们从后面开始，

第一轮：

20默认是最大开始往前比较找有没有比它还要大的值中的最大值，很显然没有，那我们继续往下面的元素8开始第二轮的对比。

第二轮：

倒数第二位的8，往前找比它大的数，与它前面所有比它大的数中的最大值【19】进行交换，8和19进行交换。

第三轮：

倒数第三位的18，往前找比它大的数，遗憾的是没有，所以就无需进行交换。

所以最终答案是： [11,7,12,14,8,1,6,18,19,20]

📝总结：