我发明了一种新的排序算法吗？还是说这和快速排序是一样的？

Question

我做了一个排序算法，但我想也许我只是重新发明了快速排序。

然而，我听说快速排序是O(N^2)个最坏情况；我想我的算法应该只有O(NLogN)个最坏情况。

这和快速排序是一样的吗？

该算法的工作原理是交换值，以便将所有小于中值的值移动到数组的左侧。然后它在每一端递归地工作。

该算法从i=0开始，j= n-1

I和j相互移动，如果需要，listi和listj将被交换。

下面是递归之前第一次迭代的一些代码：

_list = [1,-4,2,-5,3,-6]

def in_place(_list,i,j,median):
    while i<j:
        a,b = _list[i],_list[j]
        if (a<median and b>=median):
            i+=1
            j-=1
        elif (a>=median and b<median):
            _list[i],_list[j]=b,a
            i+=1
            j-=1
        elif a<median:
            i+=1
        else:
            j-=1
    print "changed to ", _list



def get_median(_list):
    #approximate median in O(N) with O(1) space
    return -4

median = get_median(_list)
in_place(_list,0,len(_list)-1,median)

"""
changed1 to  [-6, -5, 2, -4, 3, 1]
"""

Answer 1

http://en.wikipedia.org/wiki/Quicksort#Selection-based_pivoting

相反，一旦我们知道一个最坏情况的O(n)选择算法可用，我们就可以使用它在快速排序的每一步找到理想的轴心(中位数)，产生一个最坏情况下O(n

n)运行时间的变体。然而，在实际实现中，这种变体的平均速度要慢得多。

另一种变体是选择中位数的中位数作为枢轴元素，而不是中位数本身来划分元素。在保持O( n )的渐近最优运行时复杂度(通过防止最坏情况下的分区)的同时，它也比选择中值作为枢轴的变体快得多。

Answer 2

对于初学者，我假设还有其他代码没有显示，因为我非常确定您自己显示的代码不会工作。

很抱歉偷了你的火，但我担心你所显示的代码似乎是快速排序的，不仅如此，代码似乎还可能存在一些but。

考虑对相同元素列表进行排序的情况。您的_in_place方法(在快速排序中似乎是传统上称为分区的方法)不会正确地移动任何元素，但在最后，j和i似乎反映了只有一个包含整个列表的分区的列表，在这种情况下，您将在整个列表上再次递归。我的猜测是，正如前面提到的，你不会从它返回任何东西，或者看起来实际上在任何地方都是完全排序的，所以我只能猜测它将如何使用。

我担心使用真正的中值进行快速排序不仅在平均情况下可能是相当慢的策略，而且它也无法避免O(n^2)最坏的情况，同样，相同元素的列表将提供这样的最坏情况。然而，我认为使用这种中值选择算法的三向分区快速排序将保证O(n*log )时间。尽管如此，这是一个已知的选择枢轴选择，而不是一个新的算法。

简而言之，这似乎是一个不完整且可能有log的快速排序，如果没有三向分区，使用中间值将不能保证O(n*log )。然而，我确实觉得这是一件好事，值得祝贺，因为你自己确实想到了使用中位数的想法-即使别人以前也想过。