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

Question

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

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

Answer 1

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

Conversely, once we know a worst-case O(n) selection algorithm isavailable, we can use it to find the ideal pivot (the median) at everystep of quicksort, producing a variant with worst-case O(n log n)running time. In practical implementations, however, this variant isconsiderably slower on average.

Another variant is to choose the Median of Medians as the pivotelement instead of the median itself for partitioning the elements.While maintaining the asymptotically optimal run time complexity ofO(n log n) (by preventing worst case partitions), it is alsoconsiderably faster than the variant that chooses the median as pivot.