A.O(nlbn)B.O(n2)C.O(1bn)2D.O(n2lbn)

Question

A．O(nlbn)

B．O(n2)

C．O(1bn)2

D．O(n2lbn)

Answer 1

正确答案：A
解析：冒泡排序的过程很简单。首先将第1个数与第2个数相比较，若为逆序则交换两数，然后比较前两个数与第3个数，依次类推，直到将第n-1个数与第n个数比较完为止。上述过程称为一趟冒泡排序，结果是最大的数被排到了最后。然后进行第2趟，对前面n-1个数进行冒泡排序，结果是次大的数被移到了n-1的位置上。一般来说，第i趟冒泡排序是将第1个数排到了第n-i+1的位置上，整个排序过程需进行k(1≤k≤n)趟。分析冒泡排序的效率时，若初始序列为正序，则只进行一道排序，在排序过程中只进行n-1次比较，不交换数据；若为逆序，则需进行n-1趟排序，需进行n(n-1)/2次比较，交换数据的数量组也相同。因此，冒泡排序的复杂性是O(n2)。快速排序是对冒泡排序的一种改进，其基本思想是通过一趟排序将待排序的数据分成两部分，其中一部分的关键字均比另一部分的关键字小，然后再对这两部分分别进行快速排序，最后达到整个序列有序的目的。快速排序的复杂性是O(nlbn)。将题中给定的整数序列(541，132，984，746，518，181，946，314，205，827)进行从小(132，541，746，518，181，946，314，205，827，984)；对于直接选择排序，第1趟操作为984827，其结果得到的序列为(541，132，827，746，518，181，946，314，205，984)。采用快速排序(以中间元素518为基准)的第1趟扫描结果是(205，132，314，181，518，746，946，984，827)。