● 以下关于快速排序算法的描述中,错误的是 (64) 。在快速排序过程中,需要设立基准元素并划分序列

Question

● 以下关于快速排序算法的描述中，错误的是 （64） 。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素{12,25,30,45,52,67,85}构成，则初始排列为 （65） 时，排序效率最高（令序列的第一个元素为基准元素）。

（64）A. 快速排序算法是不稳定的排序算法

B. 快速排序算法在最坏情况下的时间复杂度为O(n1gn)

C. 快速排序算法是一种分治算法

D. 当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度

（65）A. 45,12,30,25,67,52,85

B. 85,67,52,45,30,25,12

C. 12,25,30,45,52,67,85

D. 45,12,25,30,85,67,52

Answer 1

正确答案：B,A
试题（64）、（65）分析
　　本题考查快速排序算法。
　　快速排序算法是一种经典的排序算法，其基本思想是选择一个基准元素（通常选择第一个元素或者最后一个元素），通过一趟排序将待排序序列分成两部分，一部分比基准元素小，一部分大于等于基准元素，此时基准元素在其排好序后的正确位置；然后再递归地排序划分的两部分，因此本质上快速排序是一种分治算法。由于在排序的过程中，各元素与基准元素比较大小，若小于基准元素则与基准元素交换位置，因此该算法是不稳定的排序算法。当每一趟排序进行后，选择的基准元素恰好最大或者最小时，就把序列分成极端不均衡的两部分，即一部分为空，另一部分为待排序序列的元素个数减1，此时算法处于最坏情况，其时间复杂度为O(n2)。当输入数据基本有序或者所有元素值相等时，不论选择第一个元素还是最后一个元素作为基准元素，都恰好把序列分成极端不均衡的两部分，快速排序算法具有最坏情况下的时间复杂度。
　　对于选项A，以45作为基准元素进行第一趟划分，先从后向前找出比45小的元素，67、52、85这三个元素保持不动，找到25，将其与45交换后，第一趟划分完成，序列为25,12,30,45,67,52,85。第二趟先对子序列25,12,30进行划分，使得25与12对调，形成子序列12,25,30；然后对67,52,85进行划分，使得67与52交换，形成子序列52,67,85。至此，整个排序过程完成。期间，第一趟划分中元素的比较次数为6次、交换1次，第二趟划分中元素的比较次数共4次、交换次数为2次，因此，排序过程中比较次数共10次，交换次数为3次。
　　对于选项B，以85作为基准元素，因12比它小，所以将85与12交换，由于剩下的元素都比85小，因此保持不动，第一趟划分之后的元素序列为12,67,52,45,30,25,85，期间元素比较次数为6次、交换1次，第二趟对85之前的6个元素进行划分，由于67、52、45、30、25都比基准元素12大，因此它们保持不动，完成第二趟划分，形成的子序列为12,67,52,45,30,25，期间比较次数为5、交换次数为0。接下来第三趟对子序列67,52,45,30,25进行划分，以67为基准元素，情况与第一趟相同，进行4次比较、l次交换后，形成子序列25,52,45,30,67。第四趟对子序列25,52,45,30进行划分，情况与第二趟相同。依此类推，完成排序时比较次数为21次（6＋5＋4＋3＋2＋1）。
　　对于选项C，以12作为基准元素，因为后面的所有元素都比它大，所以所有元素是持不动，第一趟划分之后的元素序列为12,25,30,45,52,67,85，期间元素比较次数为6次、交换0次。第二趟对子序列25,30,45,52,67,85进行划分，以25作为基准元素，因为后面的所有元素都比它大，所以所有元素保持不动，第一趟划分之后的元素序列为25,30,45,52,67,85，期间元素比较次数为5次、交换0次。接下来对子序列30,45,52,67,85进行划分，同理，元素保持不动，期间元素比较次数为4次、交换0次。依此类推，完成整个排序比较次数为21次、交换0次。
　　对于选项D，以45作为基准元素进行第一趟划分，先从后向前找出比45小的元素，85、67、52这三个元素保持不动，找到30，将其与45交换后，第一趟划分完成，序列30,12,25,45,85,67,52，期间元素比较次数为6次、交换1次。第二趟先对子序列30,12,25进行划分，以30为基准元素，30与25交换，经过2次比较、1次交换后子序列为25,12,30，需要再次对子序列25,12进行划分；同理，对子序列85,67,52进行划分后，结果为51,67,87，还需对子序列51,67进行划分。排序过程中比较次数共12次。
参考答案
　　（64）B（65）A