折半插入排序图图解

折半插入排序是一种利用二分法思想的排序算法。它通过将待插入元素与有序序列中的中间元素进行比较，从而确定待插入元素的位置，并将其插入到正确的位置上。

下面是折半插入排序的图解过程：

1. 初始状态：有一个无序序列，其中前i个元素已经是有序的。

2. 第i个元素的插入：将第i个元素与有序序列的中间元素进行比较。

- 如果第i个元素大于中间元素，则说明第i个元素应该插入到中间元素的右侧，将区间缩小为[mid+1, high]。
- 如果第i个元素小于等于中间元素，则说明第i个元素应该插入到中间元素的左侧，将区间缩小为[low, mid-1]。

3. 重复上述步骤，直到找到第i个元素的正确位置。

4. 插入第i个元素：将第i个元素插入到正确的位置上，使得前i+1个元素有序。

5. 重复以上步骤，直到所有元素都被插入到正确的位置上。

下面是折半插入排序的图解示例：

初始序列：[5, 2, 4, 6, 1, 3]

第1个元素插入：
[5, 2, 4, 6, 1, 3] -> [2, 5, 4, 6, 1, 3]

第2个元素插入：
[2, 5, 4, 6, 1, 3] -> [2, 4, 5, 6, 1, 3]

第3个元素插入：
[2, 4, 5, 6, 1, 3] -> [2, 4, 5, 6, 1, 3]

第4个元素插入：
[2, 4, 5, 6, 1, 3] -> [1, 2, 4, 5, 6, 3]

第5个元素插入：
[1, 2, 4, 5, 6, 3] -> [1, 2, 3, 4, 5, 6]

最终有序序列：[1, 2, 3, 4, 5, 6]