请用伪代码描述插入排序算法？

插入排序算法的基本思想是:

1. 将数组分为已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。

2. 取未排序区间中的元素,在已排序区间中找到其插入位置。

3. 将其插入,并调整已排序区间中被插入元素影响的元素位置。

4. 重复步骤2和3,直到未排序区间为空,排序完成。

上面的伪代码实现了这一思想:

1. 外层for循环控制趟数,每趟处理一个未排序元素。

2. 内层while循环在已排序区间中找插入位置,每找到一个更小的元素就交换一次。

3. 当退出while循环时,j的位置就是插入位置。将未排序元素插入。

4. 重复1-3步,直到数组排序完毕。

时间复杂度分析:

最好情况:数组已经有序。时间复杂度O(n)。只需要n-1趟,每趟O(1)。

最坏情况:数组逆序。时间复杂度O(n^2)。需要n-1趟,每趟O(n)。

平均情况:时间复杂度O(n^2)。

空间复杂度:O(1)。插入排序是原地排序,不需要额外空间。