快速排序算法，平均时间复杂度O（nlogn）：

python 实现：

import random
import sys   

#sys.setrecursionlimit(9)

A=[x for x in range(10000)]
random.shuffle(A)

def quick_sort(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):
    x = A[r]
    i = p-1
    for j in range(p,r):
        if A[j] <= x:
            i +=1
            A[i],A[j] = A[j],A[i]
    A[i+1],A[r] =A[r],A[i+1]
    return i+1

quick_sort(A,0,len(A)-1)
print A

random版本：

import random
import sys   

#sys.setrecursionlimit(9)

A=[x for x in range(10000)]
random.shuffle(A)

def quick_sort(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):
    x = random.randint(p,r)
    A[x],A[r] = A[r],A[x]
    i = p-1
    for j in range(p,r):
        if A[j] <= A[r]:
            i +=1
            A[i],A[j] = A[j],A[i]
    A[i+1],A[r] =A[r],A[i+1]
    return i+1

quick_sort(A,0,len(A)-1)
print A