二分插入排序的 Python 程序
pythonserver side programmingprogramming
在本文中，我们将了解下面给出的问题陈述的解决方案。
问题陈述 − 我们得到一个数组，我们需要使用二分插入排序的概念对其进行排序。
这里，顾名思义，我们使用二分搜索的概念以及插入排序算法。
现在让我们观察下面实现中的解决方案 −
示例
# sort
def insertion_sort(arr):
for i in range(1, len(arr)):
temp = arr[i]
pos = binary_search(arr, temp, 0, i) + 1
for k in range(i, pos, -1):
arr[k] = arr[k - 1]
arr[pos] = temp
def binary_search(arr, key, start, end):
#key
if end - start <= 1:
if key < arr[start]:
return start - 1
else:
return start
mid = (start + end)//2
if arr[mid] < key:
return binary_search(arr, key, mid, end)
elif arr[mid] > key:
return binary_search(arr, key, start, mid)
else:
return mid
# main
arr = [1,5,3,4,8,6,3,4]
n = len(arr)
insertion_sort(arr)
print("排序后的数组是:")
for i in range(n):
print(arr[i],end=" ")
输出
排序后的数组是: 1 3 3 4 4 5 5 6 8
所有变量均在本地范围内声明，其引用如上图所示。
结论
在本文中，我们了解了如何编写用于二分插入排序的 Python 程序
