// 升序，数组下标从 1 开始，有效范围为 a[1] ~ a[n]

// 1. 后移法
void insert_sort1(int a[], int n) {
    for (int i = 2; i <= n; i++) { 
        int key = a[i];
        int j = i - 1;

        // 将比 key 大的元素往后移动一位
        while (j >= 1 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        // 找到插入位置，将 key 放进去
        a[j + 1] = key;
    }
}

// 2. 相邻交换法
void insert_sort2(int a[], int n) {
    for (int i = 2; i <= n; i++) {
        // 将 a[i] 向左交换到正确位置
        for (int j = i; j >= 2 && a[j] < a[j - 1]; j--) {
            swap(a[j], a[j - 1]);
        }
    }
}