排序算法知识考察试卷含插入快速堆排序等要点.docx

排序算法知识考察试卷含插入快速堆排序等要点

一、单项选择题（每题5分，共100分）

1.以下哪种排序算法在最坏情况下的时间复杂度为$O(n^2)$？()

A.快速排序(正确答案)

B.归并排序

C.堆排序

D.基数排序

答案解析：快速排序在最坏情况下（例如数组已经有序且每次划分都极不平衡时）时间复杂度为$O(n^2)$；归并排序最坏情况时间复杂度为$O(nlogn)$；堆排序最坏情况时间复杂度为$O(nlogn)$；基数排序最坏情况时间复杂度为$O(d(n+r))$（d为位数，r为基数），通常也是线性级别的。

2.对于一个基本有序的数组，下面哪种排序算法效率