python3.5  

最优时间复杂度:nlog(n)

最坏时间复杂度:n²

稳定性:不稳定

1.快速排序思想:

选取第一个元素作为mid.设定两个指针,low 和 high.

low指向第一个元素,high指向最后一个元素.

low第一个指向的作为mid,high判别指向元素是否大于mid,若小于,指向元素的值赋给low,low指针再向右移动,同理.最后直到重叠,将mid值赋予此位置.

左右两边便以分成大于mid和小于mid两部分,再对两部分作同样的操作.

直到low与high重叠.停止递归

完成排序

 

2.python代码实现

def quick_sort(alist,first,last):
    '''快速排序'''
    if first >= last:
        return
    mid_value = alist[first]
    low = first
    high = last
    while low < high :
        # high左移
        while low < high and alist[high]>= mid_value:
            high-=1
        alist[low] = alist[high]
        while high > low and alist[low]<mid_value:
            low+=1
        alist[high] = alist[high]
    alist[low]=mid_value
    quick_sort(alist,first,low-1)
    quick_sort(alist,low+1,last)

if __name__=='__main__':
    li = [54,26,93,17,77,31,44,55,20]
    print(li)
    quick_sort(li,0,len(li)-1)
    print(li)