2

我正在尝试研究各种排序和搜索算法，以准备本周二即将进行的测试。一切都很顺利，直到我使用了快速排序算法。我没有书或任何其他资源，所以我上网开始阅读SparkNote。我以为我理解了文本，我什至阅读了我在网上找到的PowerPoint的快速排序算法部分。

但是，SparkNote 在算法分步过程的页面上提供了一个示例，但并没有显示最初排列列表的步骤。给出的清单是[5 9 3 8 6 4 2 1 7 0]。根据 SparkNotes，排列后的列表，左侧的值小于枢轴（即 5），右侧的值大于枢轴，是 [0 3 4 2 1 5 8 6 7 9]. 但是，当我尝试自己完成这些步骤时，我不断得到[ 4 0 3 1 2 5 6 8 7 9 ].

我采取的程序是：

5 9 3 8 6 4 2 1 7 0 // The initial list. Pivot = 5
5 0 3 8 6 4 2 1 7 9 // Switched 0 and 9.
5 0 3 1 6 4 2 1 7 9 // Switched 8 and 1
5 0 3 1 2 4 6 8 7 9 // Switched 6 and 2
4 0 3 1 2 5 6 8 7 9 // Switched 4 and 5 because the lines that point to the 
                    // greater and smaller numbers crossed.

我的错误在哪里？另外，我看到小于5的数字在左边，大于5的数字在右边，那么，我的错误真的会影响排序吗？

4

3 回答 3

3

SparkNotes 中描述的算法最初将枢轴元素放置在数组中的最右边位置。您使用的算法将枢轴放置/保持在最左边的位置。难怪分区后的安排不一样。

这意味着他们从

5 9 3 8 6 4 2 1 7 0

选择5作为枢轴并将其放置在最右边的位置（交换5和0）

0 9 3 8 6 4 2 1 7 5

只有在那之后，他们才对剩余的元素进行分区。

您将您5的位置保持在最左边（显然您只是忘记执行 SparkNotes 中的第 2 步）。最后，两种变体都有效，即没有“错误”。在您的情况下，正确分区的阵列完全有效。

于 2012-08-11T20:22:39.867 回答
1

在这里你可以看到快速排序算法的可视化实现。

也许你也会发现有用的：

如果您讨厌匈牙利民间舞蹈，请不要访问链接。:)

于 2012-08-11T20:37:51.367 回答
0

您没有遵循 sparknotes 网站上提供的确切算法。他们的第二步要求您将枢轴与最后一个元素交换。

在任何情况下，只要您拆分序列，使得枢轴之前的所有元素都小于（或等于）枢轴并且跟随它的元素更大（或平等的）。当您对生成的分区进行递归排序时，您最终会得到一个排序后的序列。

这是一个效率问题，而不是正确性问题，您如何处理相等的元素以及如何选择枢轴，以及最终以多长的序列长度切换到另一种算法。

于 2012-08-11T20:27:36.877 回答