堆排序算法,时间复杂度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