快速排序算法

Question

我用快速排序算法来排序

11 8 9 4 2 5 3 12 6 10 7

我拿到了名单：

4 3 2 5 9 11 8 12 6 10 7.

5被用作枢轴。现在我被困住了。如何对低子列表和上子列表进行排序？

pivot=5 11 8 9 4 2 5 3 12 6

• 移动到位置0 5 8 9 4 2 11 3 12 6 10 7
• i (位置1= 8)
• j (位置6= 3)⇒交换8和3 5 3 9 4 2 11 8 12 6 10 7
• i (位置2= 9)

H 111j(位置4= 2)⇒交换区9和2 5 3 2 4 9 11 8 6 10 7H 212/code>H 113i(位置3= 4) --不比5⇒交换5和H 113(位置3=4)小。4 4 3 2 5 9 11 8 12 6 10 7-在分区之后列出

Answer 1

快速排序是一种递归算法。一旦按枢轴对元素进行了排序，就会得到两组项。第一个元素的所有元素都小于或等于枢轴，第二个元素的所有元素都大于枢轴。您现在要做的是，再次将快速排序应用于这些集合中的每一组(具有适当的枢轴)。

要做到这一点，你将不得不选择一个新的支点每次。您可以做一些事情，比如总是选择第一个元素，或者随意绘制一个元素。

一旦到达一个集合只包含一个元素的点，就会停止。

理解这些事情的一个好方法是尝试使用这个算法对一副牌进行排序。所有的卡片都是朝下的，你只能一次看两张牌，比较一下，如果需要的话可以换。你必须假装不记得任何一张正面朝下的牌才能起作用。

Answer 2

该算法的一个关键组件是所选的枢轴值来自原始列表，这意味着(在您的示例中)值5的元素在第一次分区之后现在处于正确的最后位置：

4 3 2 5 9 11 8 12 6 10 7

这应该是相当明显的，并遵循简单的直觉。如果项目左侧的每个元素都小于该项，而右侧的每个元素都更大，则该项必须处于正确的排序位置。

理解整个快速排序算法所需要的洞察力是，您可以继续对每个子列表--枢轴左侧的值列表和右侧所有值的列表--进行操作，以得到最终的排序列表。这是因为：

• 每一次分区都在其正确位置上放置了另一个元素--
• ，每次迭代都从要处理的元素列表中移除一个元素--支点(这就是为什么我们最终会达到0(或1，取决于您如何执行)

的基本情况。

假设您根据以下伪代码选择了5的分区值：

Math.floor(list.length / 2)

就我们的目的而言，实际选择一个支点并不重要。这个适合你自己的选择，所以我们一起去吧。现在，让我们把这个演到最后(从你停止的地方开始)：

concat(qs([4 3 2]), 5,  qs([9 11 8 12 6 10 7])) = 
concat(qs([2]), 3, qs([4]), 5, qs([9, 11, 8, 6, 10, 7]), 12, qs([])) =
concat(2, 3, 4, 5, qs([6, 7]), 8, qs([9, 11, 10]), 12) =
concat(2, 3, 4, 5, qs([6]), 7, qs([]), 8, qs([9, 10]), 11, qs([]), 12) =
concat(2, 3, 4, 5, 6, 7, 8, qs([9]), 10, qs([]), 11, 12) = 
concat(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)

请注意，每次看到对qs的单个调用时，都会遵循以下模式：

qs(<some_left_list>), <the_pivot>, qs(<some_right_list>)

在一行上的每个qs调用都会在下一行上产生另外两个这样的调用(表示两个新子列表的处理(注意，我在单个值列表上立即分解了对qs的调用)。

自己做这个练习是个好主意。是的，用的是真正的笔和纸。