折半插入排序算法详解

折半插入排序是一种优化过的插入排序算法，它针对的是部分有序的数据集。它的基本思想不是一次比较一个元素，而是每次取数组的一半进行比较。以下是其详细步骤：

1. **初始阶段**：对于第一个元素，直接插入到已排序的部分，因为它是有序的。

2. **递归过程**：从第二个元素开始，假设当前元素为`arr[mid]`，计算中间位置`mid`。然后将数组分为两半，左半部分小于等于`mid`，右半部分大于`mid`。

3. **查找插入位置**：在左半部分使用插入排序的方式，找到第一个大于当前元素的位置`i`。如果整个左半部分都小于等于当前元素，则插入位置就是0。

4. **插入元素**：将`arr[mid]`移动到`arr[i+1]`处，使其右侧保持有序。然后继续对右半部分递归地执行此过程，直到整个数组排序完成。

5. **终止条件**：当只剩下一个元素或者整个数组已经有序时，递归结束。

折半插入排序的优点是对部分有序的数据效率较高，避免了常规插入排序需要多次移动元素的情况。然而，如果数据完全无序，它的性能仍然接近O(n^2)，因为最坏情况下的分割并不总是最优的。

相关问题

DS排序折半插入排序

### 折半插入排序算法详解

折半插入排序是一种改进的插入排序方法，其基本思想是在每一步将待排序元素通过二分查找的方式找到合适的位置并插入其中。这种方法减少了比较次数，在一定程度上提高了效率。

#### 算法原理

在传统的插入排序中，为了给新元素腾出位置，通常需要逐个向前移动较大的元素。而折半插入排序则采用二分查找来定位插入点，从而减少不必要的比较操作[^1]。

对于长度为n的数组A，从第二个元素开始遍历到第n个元素：

- 对于当前处理的元素`key=A[i]`，在其之前已经完成排序的部分序列`A[0...i-1]`里寻找合适的插入位置p；
- 使用二分查找确定位置p；
- 将位于p及其之后直到i-1处的所有元素向右平移一位；
- 插入`key`至位置p。

此过程重复执行直至整个列表有序化结束。

#### Python 实现代码

下面是基于上述逻辑编写的Python版本折半插入排序函数:

def binary_search(arr, val, start, end): 
    # 执行二分查找以获得要插入的位置
    while start <= end:
        mid = (start + end)//2
        if arr[mid] < val:
            start = mid + 1  
        elif arr[mid] > val: 
            end = mid - 1
        else:
            return mid   
    return start 

def insertion_sort_with_binary_search(array):
    for i in range(1, len(array)):
        value_to_insert = array[i]
        insert_position = binary_search(array, value_to_insert, 0, i-1)

        # 移动较大值并向后覆盖
        j = i - 1
        while j >= insert_position :
            array[j+1]=array[j]
            j -= 1
        
        # 插入目标数值
        array[insert_position] = value_to_insert
    
    return array

该实现方式不仅保持了原有插入排序稳定性特点，还因为采用了更有效的搜索策略使得性能有所提升。