3

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

但是我听说快速排序是 O(N^2) 最坏的情况；我认为我的算法应该只有 O(NLogN) 最坏的情况。

这和快速排序一样吗？

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

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

i 和 j 相互靠近，必要时交换 list[i] 和 list[j]。

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

_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]
"""
4

2 回答 2

4

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

相反，一旦我们知道最坏情况的 O(n) 选择算法可用，我们可以使用它在快速排序的每个步骤中找到理想的枢轴（中位数），从而产生最坏情况 O(n log n) 的变体运行时间。然而，在实际实现中，这种变体平均要慢得多。

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

于 2012-03-19T22:52:07.077 回答
2

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

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

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

恐怕使用快速排序的实际中位数不仅在平均情况下可能是一个相当慢的策略，它也不能避免 O(n^2) 最坏的情况，同样的元素列表会提供这样一个最坏的情况案子。但是，我认为具有这种中值选择算法的三路分区快速排序将保证 O(n*log n) 时间。尽管如此，这是枢轴选择的已知选项，而不是新算法。

简而言之，这似乎是一个不完整且可能有问题的快速排序，并且如果没有三路分区，使用中位数不能保证 O(n*log n)。但是，我确实觉得这是一件好事，值得祝贺，您自己确实想到了使用中位数的想法——即使其他人之前已经想到过。

于 2012-03-19T22:56:57.130 回答