插入排序是一种简单直观的排序算法，它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。以下是插入排序的一些关键细节和为何这种方式有效：

关键细节

1. 排序的起始点：
   插入排序从数组的第二个元素开始，即 i = 1。这是因为单个元素（数组的第一个元素）可以认为已经是排序好的。
2. 内部循环条件：
   内部循环使用 j 来比较已排序的元素和当前要排序的元素（key）。如果 key 小于 arr[j]，则说明 key 应该在 arr[j] 之前，因此 arr[j] 向后移动一个位置到 arr[j+1]，为 key 腾出空间。
3. 终止和元素插入：
   j 递减进行，直到找到 key 的正确位置。当 arr[j] 不再大于 key 或 j 减小到 -1（即 key 应该是当前已排序序列中最小的元素），循环停止。然后将 key 插入到 arr[j+1]。
4. 效率考虑：
   插入排序的效率在部分排序的数组中表现较好。在最好情况下（数组已经完全排序），它的时间复杂度为 (O(n))，因为内部循环不会执行任何操作。在平均情况或最坏情况下（数组完全反序或随机），时间复杂度为 (O(n^2))。
5. 稳定性：
   插入排序是稳定的排序算法，意味着相同元素的相对顺序不会改变。这一特性对于某些应用（如需要保持记录的相对顺序时）非常重要。
6. 就地排序：
   由于插入排序只需要一个额外的存储空间（key）进行元素的交换，它是一种就地排序算法，空间复杂度为 (O(1))。

为何有效

插入排序模仿了人们整理打乱的纸牌的方式：一个接一个地将每张牌插入到正确的位置。对于小规模或基本有序的数据集，插入排序特别有效，因为它能很快确定每个元素需要移动的位置和次数。而且，由于其简单性，它在一些场景下比更复杂的排序算法如快速排序或归并排序更加高效。

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        默认i之前的元素是排列好的
        // 将大于key的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}