单选题 (55) 在其最好情况下的算法时间复杂度为O(n)。
A．插入排序 B．归并排序 C．快速排序 D．堆排序

【正确答案】 A
【答案解析】[解析] 各种常用排序方法在最好情况下的时间复杂度如表8-2所示。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　表8-2 时间复杂度
排序方法
最好时间
直接插入
O(n)
简单选择
O(n2)
冒泡排序
O(n)
希尔排序
…
快速排序
O(nlogn)
堆排序
O(nlogn)
归并排序
O(nlogn)
基数排序
O[d(n+rd)]