使用Python语言实现快速排序算法

算法的最坏运行时间表示为：$\Theta (n^2)$

算法的期望运行时间表示为：$\Theta (n\lg n)$

快速排序算法伪算法如下：

python">'''
quick_sort(A,p,r)
    if p<r
        q=partition(A,p,r)
        quit_sort(A,p,q-1)
        quit_sort(A,q+1,r)

partition(A,p,r)
    x=A[r]
    i=p-1
    for j=p to r-1
        if A[j]<=x
            i=i+1
            exchange A[i] with A[j]
    exchange A[i+1] with A[r]
    return i+1
'''

Python算法:

python">def quick_sort(A,p,r):
    '''
    quick_sort用递归法实现对数组进行排序(正序)
    A是一个仅包含数值型的列表
    p,r是列表A的下标，且满足p<=r'''
    if p<r:
        q=partition(A,p,r)
        quick_sort(A,p,q-1)
        quick_sort(A,q+1,r)


def partition(A,p,r):
    '''
    partition为快速排序的关键函数，用来对数组进行原址重拍
    partition选择数组最后一个元素作为主元x，并围绕x把数组划分成4个(可能为空)区域
    for循环体内的下标k在每个区域满足以下性质：
    1，若p<=k<=i,则A[k]<=x
    2，若i+1<=k<=j-1,则A[k]>x
    3，若k=r，则A[k]>x
    '''
    x=A[r]
    i=p-1
    for j in range(p,r):
        if A[j]<=x:
            i=i+1
            A[i],A[j]=A[j],A[i]
    A[i+1],A[r]=A[r],A[i+1]
    return i+1        

运行结果:

python">a = [9,8,7,5,5,6,13,2,3,12]
print(a)
quick_sort(a,0,len(a)-1)
print(a)

[9, 8, 7, 5, 5, 6, 13, 2, 3, 12]
[2, 3, 5, 5, 6, 7, 8, 9, 12, 13]