汕头市做网站优化,天眼查入口,谷歌seo公司,岳阳网格员文章目录 1. 插入排序1.1 插入排序的思想1.2 插入排序的实现 2. 普通二分查找2.1 普通二分查找的思想2.2 普通二分查找的实现 3. 升级二分查找3.1 升级二分查找思想3.2 升级二分查找实现 1. 插入排序
1.1 插入排序的思想 插入排序很类似于已有一副有序的扑克牌#xff0c;不断… 文章目录 1. 插入排序1.1 插入排序的思想1.2 插入排序的实现 2. 普通二分查找2.1 普通二分查找的思想2.2 普通二分查找的实现 3. 升级二分查找3.1 升级二分查找思想3.2 升级二分查找实现 1. 插入排序
1.1 插入排序的思想 插入排序很类似于已有一副有序的扑克牌不断地通过值比较将新的扑克牌插入到有序的扑克牌中通过将新的扑克牌和有序的扑克牌进行比较。 插入排序在代码实现上可能和冒泡有点像但从算法的时间复杂度上分析插入排序会优于冒泡排序。插入排序在遇到如 [ 1 , 2 , 3 , 4 , 5 , 6 ] [1, 2, 3, 4, 5, 6] [1,2,3,4,5,6]这种数据排列时时间复杂度是常数项 选择排序和冒泡排序的时间复杂度都是 O ( n 2 ) O(n^2) O(n2)这两种排序算法都是与数据排列无关的。在遇到上述那种数据排列时还是会执行 n 2 n^2 n2次
1.2 插入排序的实现
def swap(arr, i, j):temp arr[i]arr[i] arr[j]arr[j] tempif __name__ __main__:arr [6, 3, 1, 4, 2, 5]print(原数组, arr)for i in range(1, len(arr)):for j in range(i, 0, -1):if arr[j] arr[j - 1]:continueelse:swap(arr, j, j - 1)print(排序后的数组, arr)2. 普通二分查找
在一个有序数组中找某个数是否存在
2.1 普通二分查找的思想
在一个有序数组中通过不断将数组二分来寻找最小值。
2.2 普通二分查找的实现
if __name__ __main__:arr [6, 3, 1, 4, 2, 5]print(原数组, arr)arr sorted(arr)print(排序后的数组, arr)fN 4low 0high len(arr) - 1print(想要找的数为, fN)while True:mid int((low high) / 2)if mid low or mid high:print(数不存在)breakif arr[mid] fN:flag Trueprint(数存在位于数组的第, mid, 位)break;elif arr[mid] fN:high mid - 1elif arr[mid] fN:low mid 13. 升级二分查找
在一个有序数组中找某个数最左侧的位置
3.1 升级二分查找思想
和普通二分很类似就是一点点的差异
3.2 升级二分查找实现
if __name__ __main__:arr [6, 3, 1, 4, 2, 5]print(原数组, arr)arr sorted(arr)print(排序后的数组, arr)fN 4low 0high len(arr) - 1print(想要找的数为, fN)while True:if low high:print(想要找的数最左侧位于数组的第, low, 位)mid int((low high) / 2)if mid low or mid high:print(数不存在)breakif arr[mid] fN:high mid - 1elif arr[mid] fN:low mid 1
