【算法基础】插入排序与二分查找、升级二分查找

1. 插入排序

1.1 插入排序的思想

插入排序很类似于已有一副有序的扑克牌，不断地通过值比较，将新的扑克牌插入到有序的扑克牌中（通过将新的扑克牌和有序的扑克牌进行比较）。
插入排序在代码实现上可能和冒泡有点像，但从算法的时间复杂度上分析，插入排序会优于冒泡排序。插入排序在遇到如$[1,2,3,4,5,6]$这种数据排列时，时间复杂度是常数项
选择排序和冒泡排序的时间复杂度都是$O(n^2)$，这两种排序算法都是与数据排列无关的。在遇到上述那种数据排列时，还是会执行$n^2$次

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 + 1

3. 升级二分查找

在一个有序数组中，找>=某个数最左侧的位置

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