请编写代码实现数组的插入排序。

基于比较方法的n个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是（）。

A. O(nlogn)
B. O(logn)
C. O(n)
D. O(n*n)

若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_______和记录的_____。

设用希尔排序对（98,36,-9,0,47,23,1,8,10,7）进行排序，给出的步长（也称增量序列）依次是4,2,1则排序需趟，写出第一趟结束后，数组中数据的排列次序为_______________，第二趟结束后数据的排列次序为_______________。

二分法插入排序所需比较次数与待排序记录的初始排列状态相关。（）

A. 对
B. 错

插入排序法的基本思想是__________

A. 选择一个合适的标准把数据元素分成两组，分别在组内各自排序
B. 先把数据调整成“父>=子”的完全二叉树，把根与最后一个叶交换，再重新调整
C. 每次从前往后比对相邻元素，不符合排序要求就交换
D. 每次在尚未排序的元素挑选一个最大的，与最后一个元素交换
E. 每次把一个数据添加到已排序的序列当中，并保持有序

插入排序的最好情况是________

A. 数据元素均匀分布
B. 数据元素初始是任何情况，即选择排序法不区分最好情况和最坏情况
C. 数据元素已排序
D. 数据元素逆序

插入排序的最坏情况是________

A. 数据元素均匀分布
B. 数据元素分布极不均匀
C. 数据元素已排序
D. 数据元素逆序排列

n个元素进行插入排序，最坏情况下需要移动数据元素大约________次

A. 0
B. n
C. n(n-1)/2
D. n(n-1)

插入排序法的空间复杂度________

A. 为O(1)
B. 为O(log n)
C. 为O(n)
D. 与数据元素的初始状态有关