algorithm - 快速排序 - 最坏情况

Question

我看到之前有人问过类似的问题，但我已经搜索了一段时间，似乎找不到答案。

我现在的作业是使用快速排序算法对一个包含 7 个字母的简单数组进行排序。 我们需要展示排序的每一步，每次都在枢轴下划线。 我们的讲师要求我们使用最右边 的值作为每一步的基准。 基于此视频，https://www.youtube.com/watch?v=aQiWF4E8flQ ，这是我到目前为止所拥有的(粗体轴):

GACEFBD

A|GCEFBD

AC|GEFBD

ACB|EFGD

ACBD|FGE

但我不确定从这里到哪里去。分区的左边，D是pivot，但是没有比D大的值。那么pivot到哪里去了呢？ 我看到的每个教程都使用三的中位数作为基准，或者最左边，我不是最擅长算法的。

B 部分让我们展示了使用相同规则对 ABCDEFG 进行排序的每一步。不知道从哪里开始，因为我有同样的问题。 对不起，如果这是一个愚蠢的问题。

Answer 1

考虑每次迭代会发生什么。

请记住，快速排序是这样工作的:

1. 如果数组为空，返回一个空数组并退出
2. 如果数组只有一个条目，则返回条目并退出
3. 选择一个支点
4. 将数组分成三个子数组:
   • 小于主元的值
   • 枢轴
   • 大于主元的值
5. 对于每个非空数组，再次应用快速排序并连接结果数组

(我知道我含糊地使用了“数组”这个词......但我认为这个想法很清楚)

我认为您遗漏了一个简单的事实:一旦您选择了主元，您就将它放在正确的位置，并对其他数组应用快速排序...您不需要再次对主元应用快速排序。

假设您有一个名为 QuickSort(Array, Pivot) 的函数，并且假设您始终将数组最左侧的条目作为枢轴:

• 开始:QuickSort(GACEFBD , D)
• 第一。迭代:

  [QuickSort(ACB, B), D, QuickSort(GEF, F)]

  如您所见，最右边的值可以是一个“好的”主元。

  第一次迭代后，D 已经在正确的位置

• 第二。迭代:

  [[QuickSort(A,A), B, QuickSort(C,C)], D, [QuickSort(E,E), F, QuickSort(G,G)]]

• 结果:

  [A、B、C、D、E、F、G]

妙语:即使您采用数组最右边的条目，也可能存在该条目是“好的”主元值的情况。

真正最坏的情况是对已排序的数组应用快速排序。但同样的规则适用。尝试将上述过程应用于类似这样的事情:QuickSort(ABCDEFG, G)