题5

题5

题目

快速排序算法在 ( ) 情况下最不利于发挥其长处.
A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值
C. 要排序的数据个数为奇数 D. 要排序的数据已基本有序

分析

快排的基本逻辑是二分，然后比较
基本有序了以后，那么每次选取第 n 个元素为基准，会导致划分区间分配不均匀，不利于发挥快速排序算法的优势
快速排序最怕数据已经基本有序了，因为它每次划分都会选一个元素作为基准，然后把比它小的放在左边，比它大的放在右边。
[!NOTE]
如果数据已经排好序了，每次选的基准都会把数据分成一个很小的部分（只有一个元素）和一个很大的部分（剩下的所有元素）。这样递归下去，就会类似于冒泡排序，变成了 的时间复杂度。
举个例子：
假设我们要排序的数组是 {1, 2, 3, 4, 5, 6, 7, 8}。

• 第一次划分，选 1 作为基准，结果是 {1}, {2, 3, 4, 5, 6, 7, 8}，左边只有一个元素，右边有 7 个元素。
• 然后递归分别处理两个子数组。处理左边子数组就直接结束，因为只有一个元素。处理右边子数组，选 2 作为基准，结果是 {2}, {3, 4, 5, 6, 7, 8}。
• 继续递归下去，每次都会选一个元素作为基准，把剩下的所有元素放到右边，这样每次都只处理左侧的单元素子数组，效率非常低，就相当于冒泡排序了。
  所以，快速排序在数据基本有序的情况下，效率会很低，达不到 的理想时间复杂度。
  为了避免这种情况，可以选择随机选取基准，或者在每次划分前，先对数据进行随机乱序，这样可以保证快速排序的效率。

解

D
当待排序数据为基本有序时,每次选取第 个元素为基准,会导致划分区间分配不均匀,不利于发挥快速排序算法的优势。
相反, 当待排序数据分布较为随机时, 基准元素能将序列划分为两个长度大致相等的序列, 这时才能发挥快速排序的优势。
[!NOTE]

如果数据基本有序，选择中间元素（比如4或者5）作为基准，确实可以一定程度上避免划分成极度不平衡的子数组，比选择第一个元素 1 要好很多。

但是，即使选择了中间元素作为基准，快速排序在基本有序的情况下，效率仍然会比完全随机的情况下低，只是不会像选择第一个元素那样退化到 。

让我们来具体看看为什么：

假设我们选择 4 作为基准来划分数组 {1, 2, 3, 4, 5, 6, 7, 8}：

1. 第一次划分，结果是 {1, 2, 3}, {4}, {5, 6, 7, 8}，划分还算平均。

2. 接下来，递归处理子数组 {1, 2, 3} 和 {5, 6, 7, 8}。你会发现，这两个子数组仍然是基本有序的！

这意味着，即使我们一开始选择了中间元素作为基准，在递归处理子数组的时候，仍然会面临数据基本有序的情况。虽然不会每次都划分成极度不平衡的子数组，但也很难达到每次都完美均分的理想情况。

总而言之，在基本有序的情况下，即使选择中间元素作为基准，快速排序的效率仍然会受到影响，只是不会像选择第一个元素那样退化到最坏情况。

为了尽可能提高效率，最好的方法是在每次划分前，对数据进行随机乱序，这样就几乎不会遇到数据基本有序的情况了。