选择排序简介
选择排序(Selection sort)是一种简单直观的排序算法。
简单来说就是从无序队列里面挑选最小的元素,和无序队列头部元素替换(放到有序队列中),最终全部元素形成一个有序的队列。
选择排序原理
首先在未排序序列中找到最小(大)元素,和无序队列的第一个元素替换位置,(即形成有序队列)
以此类推,直到所有元素全部进入有序队列,即排序完毕。
上代码:
def section_sort(alist):
n = len(alist)
# 定义外围循环次数
for j in range(n - 1):
# 定义min_index最小值的索引为j,目的找出最小值
min_index = j
# cur下标移动的范围,比较次数的范围限定
for i in range(j + 1, n):
# 元素比较,找出最小的值对应的索引
if alist[i] < alist[min_index]:
# 移动到最小元素的位置
min_index = i
# 保证最新的min_index不在无序队列的首位,那么就将它和无序队列的首位替换
if min_index != j:
alist[j], alist[min_index] = alist[min_index], alist[j]
if __name__ == "__main__":
alist = [9, 8, 7, 6, 5, 4, 3, 2, 1]
print("排序前:",alist)
section_sort(alist)
print("排序后:",alist)
关键点:
1、mix标签初始化:min_index = j
2、比较循环的范围:for i in range(j+1,n)
3、元素替换的条件:if min_index != j
4、排序次数范围的确定:for j in range(n-1)
时间复杂度
最优时间复杂度:O(n2)
对于无序队列选取最小元素时候,所有数值都进行了比较。所以内部的最优时间复杂度是O(n)
对于选择排序的外部循环,只和无序列表元素个数相关,元素个数是n个,,所以外部的最优时间复杂度是O(n)
所以整体来说,对于选择排序的时间复杂度就是O(n2)
最坏时间复杂度:O(n2)
因为最好的时间复杂度就是O(n2)了,所以最坏的时间复杂度还是O(n2)
稳定性: 稳定(看情况)
思考:
改那个地方,结果是降序?
if alist[i] < alist[min_index]: 代码中的 < 改为 >
本节内容小结:
1、选择排序原理:无序最小第一交换,数次over。
2、选择排序实践步骤:无序选小,小一替换-外部选择循环-异常考虑