快速排序

《算法导论》在这个整个一章中只讲了这么一个快速排序算法,快排其实本身变种很多,但是其基本思想还是一样的。

快排的基本思想主要是,先确定一个pivot,然后将所有比pivot小的元素移动到pivot左边,将比pivot大的元素移动到pivot右边,此时pivot就处于正确的位置上了,然后分别对pivot的左右部分递归地调用快排算法。

其实第一次要理解这个算法,还是挺纠结的,但是一旦理解了,实现起来还是非常简单的,具体代码如下:

#!python
def quick_sort(array,s,e):
    pivot_value = array[ (s+e)//2 ]
    if s == e:
        return 
    i = s
    j = e
    while i <= j:

        # find the item whose value is great than pivot_value
        while i <= e and array[i] < pivot_value:
            i+=1

        # find the item whose value is less than pivot_value
        while j >= s and array[j] > pivot_value:
            j-=1

        if i <= j:
           ( array[i],array[j] ) = ( array[j],array[i] )
           i += 1
           j -= 1

    # recursive
    if s <= j:
        quick_sort(array,s,j)

    if e >= i:
        quick_sort(array,i,e)

我的这个实现,并不是书上的实现,但是一样快速排序的算法,仅供参考。

惭愧的是,很久没写快排了,这个算法竟然用了半个小时才完成,真是令人汗颜~

Share on: TwitterFacebookEmail


Flyaway is the owner of this blog.

Published

Category

clrs

Tags

Contact