快速排序算法

Question

我使用了快速排序算法进行排序

11 8 9 4 2 5 3 12 6 10 7

我得到了列表：

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

使用5作为枢轴。现在我卡住了。我该如何继续对低子列表和高子列表进行排序？

枢轴=5 11 8 9 4 2 5 3 12 6 10 7

• 将枢轴移动到位置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)
• j (位置4 = 2) ⇒ 交换9和2 5 3 2 4 9 11 8 12 6 10 7
• i (位置3 = 4) – 没有比5更小的元素 ⇒ 交换5和4 4 3 2 5 9 11 8 12 6 10 7 – 分区后的列表

- Annita Zirki

---

请参考维基百科上的快速排序页面，其中有伪代码示例。还要记住，如果您需要算法，维基百科是一个不错的选择 :-) - xanatos

http://www.catb.org/jargon/html/R/recursion.html - Fred Foo

请展示您已经编写的代码以获得此结果 - 这将使帮助更加容易。 - Konrad Rudolph

Answer 1

快速排序是一种递归算法。一旦你通过枢轴对元素进行排序，你会得到两组物品。第一组包含所有小于或等于枢轴的元素，第二组包含所有大于枢轴的元素。现在，你需要对这些集合中的每一个应用快速排序（使用适当的枢轴）。

为此，你必须每次选择一个新的枢轴。你可以像“总是选择第一个元素”这样做，也可以随机选择一个。

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

理解这些内容的好方法是尝试使用该算法对一副牌进行排序。所有的牌都是面朝下的，你只能同时看两张牌，比较它们并在必要时交换它们。你必须假装不记得任何面朝下的牌才能使其工作。

- Björn Pollex

---

我需要对这两个子列表执行与初始列表相同的过程吗？ - Annita Zirki

@Annita：是的，你需要选择一个新的枢轴元素。 - Björn Pollex

每次进行交换时，我是否需要更改支点？ - Annita Zirki

左子列表是4 3 2，枢轴=4，交换4和2，得到2 3 4。这正确吗？ - Annita Zirki

@Annita：不，每次开始对新的子列表进行排序时，您都需要更改枢轴。 - Björn Pollex

左子列表是4 3 2，枢轴值为3，交换4和2，得到2 3 4。这样正确吗？ - Annita Zirki

Answer 2

算法的一个关键组成部分是所选的枢轴值来自原始列表，这意味着（在您的情况下）具有值5的元素现在在第一次分区后处于正确的最终位置：

4 3 2 5 9 11 8 12 6 10 7

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

理解整个快速排序算法所需的洞察力在于，您可以将此操作应用于每个子列表 - 枢轴左侧的值列表和包含所有值的列表 - 以到达最终排序的列表。这是因为：

• 每个分区将一个以上的元素放置在其适当的位置
• 每次迭代从要处理的元素列表中删除一个元素 - 枢轴 - （这就是为什么我们最终会达到零（或一个，具体取决于您如何执行）元素的基本情况）

假设您根据以下伪代码选择了分区值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调用进行分解）。

自己完成这个练习是一个好主意。是的，用实际的笔和纸。

- Wayne