单选题
对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为______；若采用快速排序算法，则时间和空间复杂度分别为______。
【正确答案】
C
【答案解析】[解析] 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。若数据基本有序，对插入排序算法而言，可以在近似线性时间内完成排序，时间复杂度为O(n)。对于快速排序而言，数据基本有序可以看成是最坏的情况，时间复杂度为O(n
2
)。对于两个排序算法，在排序时都需要一个额外的存储空间，因此空间复杂度均为O(1)。