选择排序
发布时间:2020-12-20 10:53:18 所属栏目:Python 来源:网络整理
导读:目录 选择排序 基本算法:一次确定一个最大值,或者最小值 二元选择排序 算法优化: 一躺确定一个最大值,一个最小值 算法改进: 如果再一轮中确认的最大值和最小值是同一个,则可以结束排序了 简单选择排序总结 简单选择排序和冒泡法的比较 选择排序 标签(空
目录
选择排序标签(空格分隔): python-排序算法 基本算法:一次确定一个最大值,或者最小值# 简单选择排序 降序排列 lst = [1,9,2,8,7,3,6,5,4] length = len(lst) # 计算长度 for i in range(length): maxindex = i # 降序排列,每次认为自己为最大值 for j in range(i+1,length): if lst[j] > lst[maxindex]: maxindex = j if i != maxindex: # 当 i != maxindex 是,再交换,可以减少几次交换 lst[i],lst[maxindex] = lst[maxindex],lst[i] print("简单选择排序实现: {}".format(lst)) 二元选择排序
算法优化: 一躺确定一个最大值,一个最小值# 二元选择排序算法 降序排列 lst = [1,4] length = len(lst) for i in range(length//2): # 这里不是 length//2+1的原因是,如果是奇数,极大值极小值交换就可以了,剩下的一定是中间值,或者,等于极大值或者极小值 maxindex = i minindex = - i - 1 minorigin = minindex for j in range(i+1,length-i): # 计算极值 if lst[j] > lst[maxindex]: maxindex = j if lst[-j-1] < lst[minindex]: minindex = -j-1 # 实现交换 if i != maxindex: lst[maxindex],lst[i] = lst[i],lst[maxindex] # 如果初始的极大值的位置是极小值,则极大值交换后,会影响极小值的位置 if i == minindex or i == length + minindex: # i == length + minindex 考虑的是 minindex是负索引的情况 minindex = maxindex if minorigin != minindex: lst[minorigin],lst[minindex] = lst[minindex],lst[minorigin] print("二元选择排序实现: {}".format(lst)) 算法改进: 如果再一轮中确认的最大值和最小值是同一个,则可以结束排序了
# 二元选择排序算法 降序排列 lst = [1,length-i): # 计算极值 if lst[j] > lst[maxindex]: maxindex = j if lst[-j-1] < lst[minindex]: minindex = -j-1 # 优化点: 如果极大值和极小值相等,则排序已经完成 if lst[minindex] == lst[maxindex]: break # 实现交换 if i != maxindex: lst[maxindex],会影响极小值的位置 if i == minindex or i == length + minindex: # i == length + minindex 考虑的是 minindex是负索引的情况 minindex = maxindex if minorigin != minindex and lst[minindex] != lst[minorigin]: # 优化点:lst[minindex] != lst[maxindex],如果值已经相同则可以不用交换了 lst[minorigin],lst[minorigin] print("二元选择排序实现: {}".format(lst)) 简单选择排序总结
简单选择排序和冒泡法的比较
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |