数据结构考研真题答案

(1)最坏时间复杂度

最坏的情况是，每个划分选择的基准是当前无序区域中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分得到的另一个非空子区间中的记录数只比划分前的无序区域少一条。

所以快速排序必须分n-1次，第一次划分开始时的区间长度为n-i+1，需要比较的次数为n-i(1≤i≤n-1)，所以总的比较次数达到最大值:

Cmax = n(n-1)/2=O(n2)

如果按照上述划分算法，每次取当前无序区的第1条记录作为基准，那么当文件的记录已经按升序(或降序)排列时，每次划分取的基准就是当前无序区中关键字最小(或最大)的记录，所以快速排序所需的比较次数最多。

(2)最佳时间复杂度

在最好的情况下，每次划分取的基准是当前无序区域的“中值”记录，划分的结果是基准的左右无序子区间长度大致相等。关键字比较总次数:

0(荷兰)

注意:

用递归树分析最好情况下的比较次数更简单。由于每次划分后左右子区间的长度大致相等，递归树的高度为O(lgn)，递归树每层上的每个节点对应的划分过程所需的关键字比较总数不超过n，所以整个排序过程所需的关键字比较总数为C(n)=O(nlgn)。

因为快速排序移动的记录数不大于比较数，所以快速排序最差的时间复杂度应该是0(n2)，最好的时间复杂度应该是O(nlgn)。