基础算法
1.冒泡排序
“”"
排序算法的稳定性介绍:
概述:
排序算法 = 把一串数据按照升序 或者 降序进行排列的 方式, 方法, 思维.
分类:
稳定排序算法:
排序后, 相同元素的相对位置 不发生改变.
不稳定排序算法:
排序后, 相同元素的相对位置 发生改变.
举例:
不稳定排序算法: 选择排序, 快速排序…
稳定排序算法: 冒泡排序, 插入排序…
冒泡排序介绍:
原理:
相邻元素两两比较, 大的往后走, 这样第1轮比较完毕后, 最大值就在最大索引处.
重复该动作, 直至排序完毕.
核心:
1. 比较的总轮数. 列表的长度 - 1
2. 每轮比较的总次数. 列表的长度 - 1 - 当前轮数的索引
3. 谁和谁比较. my_list[j] 和 my_list[j + 1]
分析流程, 假设元素个数为5个, 具体如下: [5, 3, 4, 7, 2] -> 长度为: 5
比较的轮数, i 每轮比较的次数, j
第1轮,索引:0 4 -> 5 - 1 - 0
第2轮,索引:1 3 -> 5 - 1 - 1
第3轮,索引:2 2 -> 5 - 1 - 2
第4轮,索引:3 1 -> 5 - 1 - 3
总结:
冒泡排序属于 稳定排序算法, 最优时间复杂度: O(n), 最坏时间复杂度: O(n²)
“”"
# Step1: 定义函数, 接收列表, 对其内容进行排序.
def bubble_sort(my_list):# 1. 获取列表的长度.n = len(my_list) # 假设 n = 5# 2. 定义循环, 外循环控制: 比较的轮数, 内循环控制: 每轮比较的次数.for i in range(n - 1): # i的值: 0, 1, 2, 3print(f'第 {i} 轮')# 改造1: 定义变量, 用于记录每轮 交换 的次数.count = 0for j in range(n - 1 - i): # j的值: 0123 012 01 0# 3. 具体的比较动作: 相邻元素两两比较, 大的往后走if my_list[j] > my_list[j + 1]:# 改造2: 走这里, 说明发生了交换. count += 1count += 1# 4. 走到这里, 说明索引j的值 比 索引j+1的值大, 就交换它们的位置.my_list[j], my_list[j + 1] = my_list[j + 1], my_list[j]# 改造3: 判断本轮是否发生交换, 如无交换, 说明已经拍好顺序了, 后续无需在比较.if count == 0:break# Step2: 定义列表, 测试上述的函数即可.
my_list = [5, 3, 4, 7, 2]
# my_list = [2, 3, 4, 5, 7]
# my_list = [5, 2, 3, 4, 7]print(f"排序前: {my_list}")
# 排序动作.
bubble_sort(my_list)
print(f'排序后: {my_list}')
2.选择排序
“”"
排序算法的稳定性介绍:
概述:
排序算法 = 把一串数据按照升序 或者 降序进行排列的 方式, 方法, 思维.
分类:
稳定排序算法:
排序后, 相同元素的相对位置 不发生改变.
不稳定排序算法:
排序后, 相同元素的相对位置 发生改变.
举例:
不稳定排序算法: 选择排序, 快速排序…
稳定排序算法: 冒泡排序, 插入排序…
选择排序介绍:
原理:
假设第1个元素为最小值, 定义变量min_index用于记录剩下元素中, 最小值的索引, 第一轮比较完毕后, 如果min_index的位置发生改变, 交换变量即可.
即: 第1轮比较完毕后, 最小值就在最小索引处.
大白话: 每轮比较完毕后, 最小值就在最小索引处.
核心:
1. 比较的总轮数. 列表的长度 - 1
2. 每轮比较的总次数. i + 1 ~ 列表的长度 - 1
3. 谁和谁比较. min_index 和 j 索引的元素.
分析流程, 假设元素个数为5个, 具体如下: [5, 3, 4, 7, 2] -> 长度为: 5
比较的轮数, i 每轮具体哪两个元素比较: 每轮比较的次数, j
第1轮,索引:0 0和1, 0和2, 0和3, 0和4 4
第2轮,索引:1 1和2, 1和3, 1和4 3
第3轮,索引:2 2和3, 2和4 2
第4轮,索引:3 3和4 1
总结:
选择排序属于 不稳定排序算法, 最优时间复杂度: O(n²), 最坏时间复杂度: O(n²)
“”"
# step1: 定义函数 select_sort(my_list), 对传入的列表元素进行排序.
def select_sort(my_list):# 1. 获取列表的长度.n = len(my_list) # 假设 n = 5# 2. 定义外循环, 表示: 比较的轮数.for i in range(n - 1): # i的值: 0, 1, 2, 3# 细节1: 定义变量, min_index, 用于记录: 本轮最小值的具体索引.min_index = i # 假设每轮的起始值, 都是本轮的最小值.# 3. 定义内循环, 表示: 当前元素之后所有的元素, 即: 待排序的元素.for j in range(i + 1, n): # j的值: 1234 234 34 4# 4. 如果当前的元素值 比 min_index记录的元素值还小, 就用min_index 记录当前值的索引.if my_list[j] < my_list[min_index]:min_index = j# 细节2: 走到这里, 说明一轮执行完毕, 判断min_index的索引值是否发生改变, 改变了, 就意味着: 当前元素不是最小值, 交换即可.if min_index != i:my_list[min_index], my_list[i] = my_list[i], my_list[min_index]# step2: 具体的测试动作.
my_list = [5, 3, 4, 7, 2]
# my_list = [2, 3, 4, 5, 7]
# my_list = [5, 2, 3, 4, 7]print(f"排序前: {my_list}")
# 排序动作.
select_sort(my_list)
print(f'排序后: {my_list}')
3.插入排序
“”"
排序算法的稳定性介绍:
概述:
排序算法 = 把一串数据按照升序 或者 降序进行排列的 方式, 方法, 思维.
分类:
稳定排序算法:
排序后, 相同元素的相对位置 不发生改变.
不稳定排序算法:
排序后, 相同元素的相对位置 发生改变.
举例:
不稳定排序算法: 选择排序, 快速排序…
稳定排序算法: 冒泡排序, 插入排序…
插入排序介绍:
原理:
把列表分成有序和无序的两部分, 每次从无序数据中拿到第1个元素, 然后放到对应有序列表的位置即可.
核心:
1. 比较的总轮数. 列表的长度 - 1, 即: i的值 -> 1, 2, 3, 4
2. 每轮比较的总次数. i ~ 0
3. 谁和谁比较. 索引j 和 j - 1 的元素比较.
分析流程, 假设元素个数为5个, 具体如下: [5, 3, 4, 7, 2] -> 长度为: 5
比较的轮数, i 每轮具体哪两个元素比较: 每轮比较的次数, j
第1轮,索引:1 1和0 1
第2轮,索引:2 2和1, 2和0 2
第3轮,索引:3 3和2, 3和1, 3和0 3
第4轮,索引:4 4和3, 4和2, 4和1, 4和0 4
总结:
插入排序属于 稳定排序算法, 最优时间复杂度: O(n), 最坏时间复杂度: O(n²)
“”"
# step1: 定义函数, 接收列表, 用于实现对其元素值进行排序.
def insert_sort(my_list):# 1. 获取列表的长度, 即: 比较的总轮数.n = len(my_list) # 假设, n = 5# 2. 定义外循环, 记录: 比较的总轮数.for i in range(1, n): # 此时, i的值: 1, 2, 3, 4# 3. 定义内循环, 记录: 每轮比较的总次数.for j in range(i, 0, -1): # 细节: j的值, 要+1, 因为后续的代码 由 j - 1的动作, 防止越界. j的值至少为1# 4. 判断, 如果当前元素比前个元素小, 就交换位置.if my_list[j] < my_list[j - 1]:# 具体的交换代码my_list[j], my_list[j - 1] = my_list[j - 1], my_list[j]else:# 说明j索引的值, 比 j-1的值大, 结束即可, 无需比较.break# step2: 具体的测试动作.
my_list = [5, 3, 4, 7, 2]
# my_list = [2, 3, 4, 5, 7]
# my_list = [5, 2, 3, 4, 7]print(f"排序前: {my_list}")
# 排序动作.
insert_sort(my_list)
print(f'排序后: {my_list}')
4.二分查找
“”"
二分查找解释:
概述:
二分查找也叫折半查找, 是一种效率比较高的 检索算法.
前提:
数据必须是有序的, 升序, 降序均可.
原理: 假设数据是升序的.
1. 获取中间索引的值, 然后和要查找的值进行比较.
2. 如果相等, 则直接返回True即可.
3. 如果要查找的值比 中间索引的值小, 就去 中值左 进行查找.
3. 如果要查找的值比 中间索引的值大, 就去 中值右 进行查找.
“”"
# step1: 定义函数, 表示二分查找.
def binary_search(my_list, item):"""自定义的代码, 实现: 二分查找.:param my_list: 有序的数据 列表:param item: 要查找的元素.:return: True-> 找到了, False->没找到."""# 1. 获取列表的长度.n = len(my_list)# 2. 判断如果列表的长度为0, 则: return Falseif n <= 0:return False# 3. 定义变量, 记录: 中间索引.mid = n // 2# 4. 判断要查找的值 和 中间索引值 的关系.if item == my_list[mid]:# 相等, 直接返回结果即可.return Trueelif item < my_list[mid]:# 要查找的值 小于 中间索引的值, 去 中值左 进行查找.return binary_search(my_list[:mid], item) # middle: 中间的意思.else:# 要查找的值 大于 中间索引的值, 去 中值右 进行查找.return binary_search(my_list[mid + 1:], item) # middle: 中间的意思.# 5. 走到这里, 说明整个列表查找完毕还没有找到, 返回False即可.return False# step2: 测试代码.
my_list = [2, 3, 5, 9, 13, 27, 31, 39, 55, 66, 99]
# my_list = []
print(binary_search(my_list, 39))
print(binary_search(my_list, 55))
print(binary_search(my_list, 100))
print(binary_search(my_list, 22))5.二分查找 非递归
“”"
二分查找解释:
概述:
二分查找也叫折半查找, 是一种效率比较高的 检索算法.
前提:
数据必须是有序的, 升序, 降序均可.
原理: 假设数据是升序的.
1. 获取中间索引的值, 然后和要查找的值进行比较.
2. 如果相等, 则直接返回True即可.
3. 如果要查找的值比 中间索引的值小, 就去 中值左 进行查找.
3. 如果要查找的值比 中间索引的值大, 就去 中值右 进行查找.
二分查找的时间复杂度: O(logn)
“”"
# step1: 定义函数, 表示: 二分查找_非递归版.
def binary_search(my_list, item):# 1. 定义变量start 和 end, 分别记录列表的第1个 和 最后1个元素的索引.start = 0end = len(my_list) - 1# 2. 循环查找, 只要 start <= end, 就一直找.while start <= end:# 3. 定义变量mid, 记录: 中间索引.mid = (start + end) // 2# 4. 判断要查找的值 和 中间值的关系.if item == my_list[mid]:# 相等直接返回即可.return Trueelif item < my_list[mid]:# 要查找的值比 中间值小, 去 中值左 进行查找.end = mid - 1else:# 要查找的值比 中间值大, 去 中值右 进行查找.start = mid + 1# 5. 循环结束, 并没有找到, 返回False.return False# step2: 测试函数.
my_list = [2, 3, 5, 9, 13, 27, 31, 39, 55, 66, 99]
# my_list = []
print(binary_search(my_list, 39))
print(binary_search(my_list, 55))
print(binary_search(my_list, 100))
print(binary_search(my_list, 22))
坚持分享 共同进步 如有错误 欢迎指出
