做网站法人拍照背景,做空间的网站,wordpress 导入工具插件,北滘网站设计一、选择排序——时间复杂度
定义#xff1a;第一趟排序#xff0c;从整个序列中找到最小的数#xff0c;把它放到序列的第一个位置上#xff0c;第二趟排序#xff0c;再从无序区找到最小的数#xff0c;把它放到序列的第二个位置上#xff0c;以此类推。 也就是说第一趟排序从整个序列中找到最小的数把它放到序列的第一个位置上第二趟排序再从无序区找到最小的数把它放到序列的第二个位置上以此类推。 也就是说首先从序列中找到最小的元素放到有序区的第一个位置上然后再从剩下的无序区中继续找最小的元素放到有序区的末尾。
1、容易想到的方法——不推荐 新建一个空列表然后每遍历一次老列表时候就把一个最小值放到新列表里同时再把这个值从老列表里删除掉。
但这种方法有两个缺点
1额外占内存。因为新建了一个空列表 l1所以就会多占用一个内存空间。
2时间复杂度高排序效率慢。 列表的增加和删除方法时间复杂度都是O(n)。 原因把最小值加到新列表里首先要先找到最小值而找最小值的过程其实就是把所有值都遍历一遍所以增加的操作时间复杂度式O(n)。 同理对于删除操作也一样你要删掉最小值首先得找到而找最小值的过程就是要把列表全部遍历一遍时间复杂度也是O(n)。 所以法1中增加和删除操作它俩时间复杂度其实也就是O(n)O(n)因为他俩是并行运行的不是嵌套运行所以结果还是O(n)。外面还有一个for循环所以法1代码复杂度就是。
# 法1
def select_sort_simple(li): l1 []for i in range(len(li)): # 时间复杂度o(n)l1.append(min(li)) li.remove(min(li)) return l1result select_sort_simple([5, 3, 7, 2, 4])
print(result)# 结果
[2, 3, 4, 5, 7] 或许你会说把最小值赋值给一个变量比如amin(li)然后每次增加删除这个值结果还一样吗答案是肯定一样的因为你即使把它赋值给一个变量但前提你也得先找到这个最小值而找最小值的过程就是把列表所有值都遍历一遍此时它的复杂度就已经是了再加上外面的for循环代码整体复杂度还是。
# 法2 最小值赋值给一个变量
def select_sort_simple(li): l1 []for i in range(len(li)): # 时间复杂度 O(n)amin(li) # 时间复杂度 O(n)l1.append(a) li.remove(a) return l1result select_sort_simple([5, 3, 7, 2, 4])
print(result)
# 结果同上
2、使用切片的方式控制无序区——推荐 使用切片的方式控制无序区每一趟排序后都将无序区中的最小值放到无序区的第一个位置也就是说把无序区的最小值跟无序区的第一个元素进行交换此时这个最小值也就自然放到了有序区的末尾。
跟上面方法相比虽然时间复杂度一样但是不用新建空列表。
# 推荐
def select_sort(li): for i in range(len(li) - 1): # 总共要排n-1趟min_val min(li[i:]) # !!! 每遍历一次无序区就会少一个数a li.index(min_val) # 找到最小值的下标li[i], li[a] li[a], li[i] # 每趟遍历就把最小值与这趟对应位置上的数进行交换# 或者说就是把无序区的最小值与无序区第一个数进行交换return liresult select_sort([5, 1, 2, 4])
print(result)
# 结果
[1, 2, 4, 5]
效果图 当然也可以输出每趟排序的结果结果跟上图也是一样的
def select_sort(li):for i in range(len(li) - 1): # 总共要排n-1趟min_val min(li[i:]) a li.index(min_val) # 找到最小值的下标li[i], li[a] li[a], li[i] print(li) # 每趟排序后的结果return liresult select_sort([5, 1, 2, 4])
print(最终排序结果, result)# 结果
[1, 5, 2, 4]
[1, 2, 5, 4]
[1, 2, 4, 5]
最终排序结果 [1, 2, 4, 5]
上面方法中使用的是切片来控制无序区的大小或者叫范围然后再从这个范围里找最小值这里呢我们也可以使用 for 循环的形式来控制无序区的范围。代码如下
这个跟上面方法类似但利用切片方式控制无序区范围相比for循环会更加简洁明了所以推荐切片的方法。
def select_sort(li):for i in range(len(li) - 1): # 总共要排n-1趟min_loc i # 假设无序区的第一个数是最小数for j in range(i1, len(li)): # 遍历无序区if li[j] li[min_loc]: # 如果无序区中有个数比无序区第一个数小min_loc j # 改变最小值的下标li[i], li[min_loc] li[min_loc], li[i] # 将无序区第一个数与最小数进行交换print(li) # 每趟排序后的结果return li# result select_sort([3, 4, 2, 1, 5, 6, 8, 7, 9])
result select_sort([5, 1, 2, 4])
print(最终排序结果, result)# 结果
[1, 5, 2, 4]
[1, 2, 5, 4]
[1, 2, 4, 5]
最终排序结果 [1, 2, 4, 5]
