在编程的世界里，我们总是在寻找更高效的方式来解决问题。今天，让我们一起探索一种改进版的插入排序算法——折半插入排序（Binary Insertion Sort）。这是一种结合了二分查找和插入排序优点的算法，能够在一定程度上提高排序效率。
首先，我们来回顾一下什么是插入排序。插入排序是一种简单直观的排序方法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。而折半插入排序则是在插入时利用二分查找法确定插入位置，从而减少比较次数。
接下来，让我们看看如何用Python实现这一算法：
```python
def binary_search(arr, val, start, end):
二分查找，返回合适的位置
if start == end:
if arr[start] > val:
return start
else:
return start + 1
if start > end:
return start
mid = (start + end) // 2
if arr[mid] < val:
return binary_search(arr, val, mid + 1, end)
elif arr[mid] > val:
return binary_search(arr, val, start, mid - 1)
else:
return mid
def insertion_sort(arr):
for i in range(1, len(arr)):
val = arr[i]
j = binary_search(arr, val, 0, i - 1)
arr = arr[:j] + [val] + arr[j:i] + arr[i+1:]
return arr
示例
arr = [37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54]
print("原始数组:", arr)
sorted_arr = insertion_sort(arr)
print("排序后的数组:", sorted_arr)
```
上面的代码展示了如何使用折半插入排序对一个数组进行排序。通过这种方式，不仅能够保持插入排序原有的简单性，还能在某些情况下显著提升性能。
希望这篇简短的介绍能帮助你理解折半插入排序的基本概念和实现方法！🚀✨