堆排序算法,时间复杂度O(nlogn):

python实现:

import random
import sys   

#sys.setrecursionlimit(9)

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

def build_max_heap(A,heap_size):
    
    for i in range(((heap_size)/2),-1,-1):
        max_heapify(A,i,heap_size)

def max_heapify(A,i,heap_size):
    l = 2*i +1
    r = 2*i +2

    if l< heap_size and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r< heap_size and A[r] > A[largest]:
        largest = r
    if largest !=i:
        A[i],A[largest] = A[largest],A[i]
        max_heapify(A,largest,heap_size)

def heap_sort(A,heap_size):
    build_max_heap(A,heap_size)
    for i in range(heap_size-1,0,-1):
        A[0],A[i] = A[i],A[0] 
        heap_size -=1
        max_heapify(A,0,heap_size)


heap_sort(A,len(A))
print A