[算法学习]之quicksort

    好长时间没有写算法之类的代码了。（貌似也没写过啥算法）

    晚上看书的时候想要检验一下自己老了木有，随手写一个试试

    当然，表面上看快拍简单，但是调试了一点时间，100w的数组，排序需要14s左右。

def swap(array, x, y):
    array[x],array[y] = array[y],array[x]

def partition(array, begin, end):
    pivo = array[begin]
    l = begin
    for i in xrange(begin + 1, end):
        if array[i] > pivo: continue
        l += 1
        swap(array, i, l)
    swap(array, begin, l)
    return l

def qsort(array, begin, end):
    if begin >= end: return
    mid = partition(array, begin, end)
    qsort(array, begin, mid)
    qsort(array, mid + 1, end)

def main():
    import random
    array = [random.randint(1, 1000000) for i in xrange(1000000)]
    qsort(array, 0, len(array))
    for i in xrange(1, len(array)):
        assert array[i-1] <= array[i]
    print 'ok'

if __name__ == '__main__':
    main()