• 插入排序思想：每次将一个待排序的记录，按照值的大小插入到已排序好的数组中的适当位置，知道全部记录插入完毕
• 插入排序是稳定的，时间复杂度为O(n2)

#import <iostream>
using namespace std;

void insertSort(int nums[], int n) {
    int i, j;
    for (i = 1; i < n; i++) { //nums[0]自成一个序列，从nums[1]开始插入
        if (nums[i] < nums[i - 1]) { //nums[i]符合插入条件
            int temp = nums[i];
            for (j = i - 1; j >= 0 && nums[j] > temp; j--) {
                nums[j + 1] = nums[j];
            }
            nums[j + 1] = temp;
        }
    }
}

int main() {
    int n;
    cin>>n;
    int nums[n];
    for (int i = 0; i < n; i++) { //输入未排序的数
        cin>>nums[i];
    }
    
    insertSort(nums, n);
    
    for (int i = 0; i < n; i++) { //输出排序完毕的序列
        cout<<nums[i]<<" ";
    }
    cout<<endl;
    return 0;
}