C++插入排序的算法理解

插入排序是一种简单直观的排序算法，它的工作原理是将数组分为已排序和未排序两部分，然后每次从未排序的部分取出一个元素，插入到已排序部分的正确位置，使其保持有序。下面是插入排序的基本步骤：

1. **初始阶段**：假设第一个元素是已排序的，其余元素为未排序。
2. **遍历阶段**：从第二个元素开始，对于每个元素（称为“关键字”）：
a. **比较过程**：将当前元素与已排序部分的所有元素依次比较，直到找到一个比当前元素小（或相等，如果按升序排序）的位置。
b. **插入操作**：将当前元素移动到该位置，使得较小的元素在前面。
3. **重复**：继续以上步骤，直到所有元素都被插入到正确的位置。

**算法伪代码**：

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        // 将 arr[j] 向右移动，找到正确的位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;  // 插入关键元素
    }
}

**相关问题**:
1. 插入排序适用于什么样的数据场景？
2. 插入排序的时间复杂度是多少？对于已经部分排序的数组，它的性能如何？
3. 插入排序相较于其他排序算法（如快速排序、归并排序）有什么优缺点？