在原始序列已经有序(升序或降序)的情况下,(60)算法的时间复杂度为O(n2)。A.堆排序B.插入排序C.快

Question

在原始序列已经有序(升序或降序)的情况下，(60)算法的时间复杂度为O(n2)。

A．堆排序

B．插入排序

C．快速排序

D．归并排序

Answer 1

正确答案：C
解析：无论原始序列中的元素如何排列，归并排序和堆排序算法的时间复杂度都是 O(nlgn)。快速排序算法处理的最好情况指每次都是将待排序列划分为均匀的两部分，此时算法时间复杂度是O(nlgn)。在原始序列已经有序(升序或降序)的情况下，快速排序算法的时间复杂度反而为O(n²)。插入排序是将一个新元素插入已经排列好的序列中。如果在数据已经是升序的情况下，新元素只需插入到序列尾部，这就是插入排序的最好情况，此时计算时间为O(n)。