时间戳

首页 > 解决方案 > 使用中值 3 方法进行快速排序的最坏情况

algorithm - 使用中值 3 方法进行快速排序的最坏情况

问题描述

我们能否始终避免使用中值 3 方法进行快速排序的最坏情况？

标签： algorithmsortingtimetime-complexityquicksort

解决方案

快速排序算法的工作原理如下：

  1. 如果 S 中的元素个数为 0 或 1，则返回（基本情况）。
  2. 选择 S 中的任何元素 v（称为枢轴）。
  3. 将 S 中除 v 之外的元素分成两个不相交的组
  4. 返回 {快速排序(S1) + v + 快速排序(S2)}

使用3个中位数方法快速排序的最坏情况是，当所选枢轴将问题大小降低最小的量时。这意味着选定的枢轴提供尽可能远的分区。并且由于我们使用的是中值 3 方法，因此所选分区不能是最大或最小元素，因为我们选择的方法确保分区具有大于和小于中位数的元素。

因此，如果您的意思是我们能否避免真正的 O(n^2) 场景的最坏情况，其中每个元素按向后值顺序排列并且我们必须对整个列表进行分区，那么是的，我们可以避免最坏的情况。

使用中值 3 方法的目的是让我们更接近快速排序的平均运行时间：O(nlogn)。这是因为通过避免列表中最远的元素来选择我们的分区，我们可以最小化我们与 O(nlogn) 的最佳/平均案例运行时间的偏差。

使用 3 的中值方法将使我们不必在整个列表中搜索正确的分区，而是从中间的某个位置开始。因此，我们可以避免 O(n^2) 的最坏情况运行时间并稳定在 O(nlogn) 的平均运行时间

推荐阅读