这用什么分区算法？（用于快速排序）

我正在研究"Quick as a Flash" over at CodeEval，我试图找出他们用于分区步骤的算法。 The only hint is the animation they include.这用什么分区算法？（用于快速排序）

它看起来是递归的，但我不知道逻辑是什么。它似乎没有按照维基百科的标准“Lomuto”分区方案。

任何指针将不胜感激，没有破坏者如何完成挑战，我想自己完成它;但是，这个帖子中没有足够的信息可以继续。

编辑：

这里它显示在动画列表的状态之间的转变：

5,2，6,1，3，4
4，2,6 ，1，3，5
4,2，5，1，3，6
4，2，3，1，5，6
1，2，3，4，5，6

（然后重复）

来源

2016-03-22 mathFromtheGroundUp

[链接到维基百科文章的Lumoto方法。 ]（https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme） – mathFromtheGroundUp

[链接到同一篇文章中备用分区方案的图形。]（https://en.wikipedia.org/wiki/File:Quicksort -diagram.svg） – mathFromtheGroundUp

基于该动画，他们在选择所述第一元件作为pivot每一次，然后基于所述pivot的值交换的值。枢轴左侧的值将会更小，右侧的值应该更大。我没有透露答案，但下面的代码只是你的开始！

下面的代码片段是为quicksort算法

def partition(A, start, end): 
    pivot = A[end] 
    pindex = start 
    for i in range(start, end): 
     if A[i] <= pivot: 
      A[i], A[pindex] = A[pindex], A[i] 
      pindex += 1 

    A[pindex], A[end] = A[end], A[pindex] 
    return pindex 

def quick_sort(A, start, end): 

    if start < end: 
     pindex = partition(A, start, end) 
     quick_sort(A, start, pindex - 1) 
     quick_sort(A, pindex + 1, end) 

    return A 

print quick_sort([10, 1, 2, 1, 1, 1], 0, 5)

来源

2016-03-22 19:41:41 python

感谢您的回复。我已经实现并测试了Lumoto方法（就像这里一样），并且它不按照动画对列表进行排序。我假设分区步骤是决定排序过程中找到多少枢轴点的关键，这将改变我对CodeEvals的答案？我有一所蹩脚的学校，所以我们没有以任何方式研究这种类型，所以我不确定我说的是否正确。=/ – mathFromtheGroundUp

我只是用CodeEval检查了两次，分区算法似乎影响了一些测试的结果。他们提供的样本数据可以正确使用Lumoto方法（如此处）并正确地确定正确的枢轴数。但是他们在测试答案期间使用的其他数据却不尽相同：我的最后一次执行得到了〜45/100。我无法用格式化他们的“结果”页面的方式来检查错误，所以我无法知道它们如何以及它们之间的差异。 = / – mathFromtheGroundUp

显然，问题仅仅是可怕的破坏：

https://getsatisfaction.com/codeeval/topics/as-quick-as-a-flash （codeeval的反馈系统）

抱歉没有发现越早，但显然获得满意的投递系统没有被Google正确编入索引;由于我以前在他们的网站或通常通过谷歌寻求帮助的尝试都没有显示出这个结果。 > <

我会标记python的答案是正确的，因为它是有用的，非常接近我所要求的。

在任何情况下，解决问题的方法是使用霍尔分区方案，虽然这是不可能的从问题中给出的信息来推断：

https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

来源

2016-03-26 19:55:03 mathFromtheGroundUp

这用什么分区算法？ （用于快速排序）

回答

相关问题

这用什么分区算法？（用于快速排序）