啥？选择排序还能这样写，太强！
一、 Day2 总结
我的《算法刷题日记》知识星球，Day2 星球内的朋友们打卡非常积极，截止目前已经有 100多 位提交代码打卡。下面是今天部分打卡的截图：
之所以放上这些截图，是帮助大家更加方便辨别我的这个星球是否对你真正有用。
下面总结下 Day2：选择排序算法，以下主要参考：@川 顺 页，@Leven 两位球友的打卡总结。
1.1 算法步骤
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
1.2 这种性能差
有一部分球友提交了下面这个版本，此代码中虽然也没有太大问题，但是循环中只要找到小的就交换一次，增加了内存占用。
实际应该为在单次循环时不进行位置交换，而是单次循环后再进行位置交换
def select_fun(list1):
n = len(list1)
for i in range(n-1): # 开启循环，只需要循环n-1次即可,
# 假设第i个值为最小值，min_value = list1[i]
for j in range(i+1, n): # j 输入i后面的数字
if list1[j] < list1[i]: # 如果发现后面存在比最小值档还小的数
list1[i], list1[j] = list1[j], list1[i] # 交换顺序
return list1
if __name__ == '__main__':
list2 = [3, 5, 6, 1, 2]
print(select_fun(list2))
"""
# 输出结果
[1, 2, 3, 5, 6]
"""
1.3 这种性能良
大部分球友提交的代码实现版本：
def select_fun(list1):
n = len(list1)
count = 0 # 统计更改次数
for i in range(n-1): # 开启循环，只需要循环n-1次即可,
min_index = i
for j in range(i+1, n): # j 输入i后面的数字
if list1[j] < list1[min_index]: # 如果发现后面存在比最小值档还小的数
min_index = j # 这里暂时不更改位置，等循环结束后再更改
if min_index != i: # 判断当前的最小值是不是i所在位置
list1[i], list1[min_index] = list1[min_index], list1[i]
count += 1
print('交换次数', count)
return list1
if __name__ == '__main__':
list2 = [3, 5, 6, 1, 2]
print(select_fun(list2))
"""
# 输出结果
交换次数 4
[1, 2, 3, 5, 6]
"""
1.4 性能更好的实现
@Leven 打卡代码：同时找出最小值与最大值放在数列两侧，两边逐渐逼近，循环次数会减少一些。
二、 Day3 作业题
零基础入门算法，首先需要搞清楚下面基本问题：
什么是一个算法？ 程序就等于算法吗？
理解以上参考清华大学邓俊辉老师的视频：
https://next.xuetangx.com/learn/THU08091000384/THU08091000384/1516243/video/1387095
理解以上参考清华大学邓俊辉老师的课程。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-05-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录