快速排序

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

快排的基本思想主要是，先确定一个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: Twitter ❄ Facebook ❄ Email

---

---