快速排序算法：我不断得到一个不同的答案

我正在努力研究本周二即将到来的测试的各种排序和搜索算法。一切都很顺利，直到我找到了快速排序算法。我没有书或任何其他资源，所以我上网并开始阅读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的数字在右边，所以，我的错误是否真的影响了排序？

来源

2012-08-11 kullalok

有很多不同的方法来分区快速排序数组。只需Google“quicksort分区”即可找到多个示例。 – Blastfurnace 2012-08-11 20:27:50

SparkNotes中描述的算法最初将主元素放置在数组中最右边的位置。您使用的算法放置/保持关键点位于最左边的。难怪分区之后的安排是不同的。

这意味着，它们开始与

5 9 3 8 6 4 2 1 7 0

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

0 9 3 8 6 4 2 1 7 5

只有经过它们进行分割为其余元素。

您在最左边的位置（显然你只是忘记从的SparkNotes执行步骤2）保持你的5。最后，两种变体都可以工作，即没有“错误”。在你的情况下，这个安排对阵列正确分区是完全有效的。

来源

2012-08-11 20:22:39 AnT

您没有按照精确算法上的SparkNotes站点呈现。他们的第二步要求您将枢轴与最后一个元素交换。

在任何情况下，对于算法而言，如何精确执行分区都是无关紧要的，只要您将该序列分割为使得所有元素在主元之前都小于（或等于）主元和其后的元素更大（或相等）。当你递归地对结果分区进行排序时，你最终会得到一个排序序列。

它的效率，而不是正确的事，你如何处理等元素，以及如何选择枢轴，以及在什么序列长度你最终切换到另一种算法。

来源

2012-08-11 20:27:36

Here你可以看到视觉实施Quick-sort算法。

也许你还会发现有用：

如果你恨匈牙利民间舞蹈不要去链接。 :)

来源

2012-08-11 20:37:51

快速排序算法：我不断得到一个不同的答案

回答

相关问题