单选题
直接选择排序的平均时间复杂度为 (17) 。最好情况下时间复杂度为O(n)的排序算法是 (18) 。在最好和最花情况下的时间复杂度均为O(nlogn)且稳定的排序方法是 (19) 。
【正确答案】
C
【答案解析】[解析] 排序算法的时间复杂度是用元素的平均比较次数和元素的平均移动次数来衡量的,它是排序算法的主要标准。冒泡排序在正序情况下只要进行一趟排序即可;在这一趟排序中,只进行n-1次比较,不需要移动元素。
快速排序和堆排序都是不稳定的排序方法;归并排序和基数排序则是稳定的排序方法。基数排序的时间复杂度为0(d(n+ r))(其中n为记录数,r为基数,d为关键字分量数),归并排序的时间复杂度在最好和最坏情况下均为0(nlogn)。