algorithm - 我发明了一种新的排序算法吗？或者这和快速排序一样吗

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

但是我听说快速排序是 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]
"""

最佳答案

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

关于algorithm - 我发明了一种新的排序算法吗？或者这和快速排序一样吗，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9779011/