倒序插入法（也称为倒插排序）是一种改进的插入排序算法，其核心思想是从待排序序列的末尾开始向前遍历，将每个元素插入到已排序部分的适当位置。以下是详细的计算步骤及Python实现示例：
一、算法步骤
初始化 将待排序序列的第一个元素视为已排序部分，其余元素为未排序部分。
从后向前遍历
从待排序序列的最后一个元素开始，向前遍历每个元素。
插入操作
对于当前元素`arr[i]`，在已排序部分（`arr`到`arr[i-1]`）中从后向前扫描。
找到第一个小于或等于`arr[i]`的元素位置`j`。
将`arr[i]`插入到位置`j`，并将`arr[j]`及之后的元素向后移动一位。
重复步骤2和3
继续向前遍历，直到所有元素都被插入到已排序部分。
完成排序
遍历完成后，整个序列即为有序序列。
二、Python实现示例
```python
def insertion_sort_descending(arr):
n = len(arr)
for i in range(n - 1, 0, -1): 从后向前遍历
key = arr[i]
j = i - 1
找到第一个小于或等于key的位置
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key 插入key
return arr
示例
arr = [6, 3, 8, 2, 9, 1, 7]
sorted_arr = insertion_sort_descending(arr)
print("Sorted array is:", sorted_arr)
```
三、示例解析
以数组`[6, 3, 8, 2, 9, 1, 7]`为例：
初始状态： 已排序部分：`` 未排序部分：`[3, 8, 2, 9, 1, 7]` `key=1`，与已排序部分比较，找到插入位置`j=0`，插入后数组变为`[1, 3, 8, 2, 9, 6, 7]` `key=6`，与已排序部分比较，找到插入位置`j=5`，数组保持不变`[1, 3, 8, 2, 9, 6, 7]` 继续向前遍历，最终得到有序数组`[1, 2, 3, 6, 7, 8, 9]` 四、时间复杂度 最坏情况： O（n²）（当序列逆序时） 平均情况第一轮遍历（i=6）
第二轮遍历（i=5）
后续遍历
最好情况：O（n）（当序列已排序时）
五、空间复杂度
空间复杂度：O（1）（原地排序）
倒序插入法通过减少元素移动次数，理论上比正序插入排序性能更好，但整体时间复杂度仍为平方级，适用于小规模数据排序。