数据结构直接插入排序算法

直接插入排序是一种简单的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。以下是直接插入排序的步骤：

1. **基础步骤**：假设有一个数组，初始状态下数组是无序的。
2. **遍历**：从第二个元素开始（索引为1），对每个元素执行插入操作。
3. **插入操作**：将当前元素（`arr[i]`）与前面已排序的元素比较，如果`arr[i]`比前一个元素`arr[i-1]`小（或大，具体取决于排序规则，这里是升序），就逐个交换它们的位置，直到找到正确的位置使整个序列保持有序。
4. **重复**：重复这个过程，直到所有的元素都被插入到正确的位置，形成一个有序数组。

**伪代码**示例：

for i = 1 to arr.length:
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
        arr[j + 1] = arr[j]
        j = j - 1
    arr[j + 1] = key

**相关问题**:
1. 插入排序适用于什么样的数据分布情况？
2. 直接插入排序和冒泡排序有什么区别？
3. 插入排序的时间复杂度是多少？
4. 当输入数组已经是部分有序时，直接插入排序的优势是什么？