规则

1，从第一个元素开始，该元素被认为已被排序

2，储存下一个元素的值，在已排序的序列中从后往前扫描

3，如果前一个元素的值大于已储存元素的值，将前一个元素的值赋给（复制到）它的后一位

4，重复步骤3，直到找到已排序的元素不大于新元素的位置，插入新元素到该位置

5，插入新元素后，重复步骤2~5

#include<iostream>
using namespace std;
int arr[10005] = { 0 };
int main()
{int n = 0;int j = 0;int i = 0;int key = 0;cin >> n;for (i = 1; i <= n; i++)cin >> arr[i];for (i = 2; i <= n; i++){key = arr[i];j = i - 1;//将i-1的值储存在j中，改变j的值而不改变i的值while (j >= 1 && key < arr[j])//如果第下一个数比第当前的数小，就把下一个数的值赋给第当前的数//*或者当循环到第一个数时停止循环{arr[j + 1] = arr[j];j--;//j--用于开始比较上一个数与上上个数的大小，同时检测是否已经比较了第1，2个数}arr[j + 1] = key;//当下一个数比当前的数大时，停止while循环，把key储存的值赋给当前的数//*或者当循环到第一个数时把key储存的值赋给第一个数}for (i = 1; i <= n; i++)cout << arr[i] << ' ';return 0;
}

示例 

输入3 5 9 1 7 0

输出0 1 3 5 7 9

总结

每次输入新数字，大数字往后排