首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
重复第二步,直到所有元素均排序完毕。
选择排序对冒泡排序进行了改进,保留了其基本的多趟比对思路,每趟都使当前最小项就位。 但选择排序对交换进行了削减,相比起冒泡排序进行多次交换,每趟仅进行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²)。但是,由于减少了交换次数,因此选择排序算法通常更快。
选择排序可以先排小的再排大的,也可以逆过来先排大的再排小的。
👇下面是我的解题思路:
这道题,我们可以一眼看出它是先排大的数再排小的数,因为如果先排小的数,应该是先排1,很明显没有这个选项。
所以,我们从后面开始,
第一轮:
20默认是最大开始往前比较找有没有比它还要大的值中的最大值,很显然没有,那我们继续往下面的元素8开始第二轮的对比。
第二轮:
倒数第二位的8,往前找比它大的数,与它前面所有比它大的数中的最大值【19】进行交换,8和19进行交换。
第三轮:
倒数第三位的18,往前找比它大的数,遗憾的是没有,所以就无需进行交换。
所以最终答案是: [11,7,12,14,8,1,6,18,19,20]