对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是（ ）。

Question

A.冒泡排序为n／2
B.冒泡排序为n
C.快速排序为n
D.快速排序为n(n-1)／2

Answer 1

【答案】：D

冒泡排序法首先将第一个记录的关键字与第二个记录的关键字进行比较，若逆序则交换，然后比较第二个与第三个，依此类推，直至第n一1个与第n个记录的关键字进行比较。在最坏情况下，冒泡排序中，若初始序列为“逆序”序列，需要比较n(n一1)/2次。快速排序是对通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字比另一部分记录的关键字小，然后分别对这两部分记录继续进行排序，最终达到整个记录有序。最坏情况下比较次数为n(n一1)/e。