2011年11月26日 星期六

Heap Sort

def sort(number):
tmp = [0] * (len(number) + 1)
for i in range(1, len(tmp)):
tmp[i] = number[i - 1]
doHeap(tmp)
m = len(number)
while m > 1:
tmp[1], tmp[m] = tmp[m], tmp[1]
m -= 1
p = 1
s = 2 * p
while s <= m: if s < m and tmp[s + 1] < tmp[s]: s += 1 if tmp[p] <= tmp[s]: break tmp[p], tmp[s] = tmp[s], tmp[p] p = s s = 2 * p for i in range(len(number)): number[i] = tmp[i + 1] def doHeap(tmp): heap = [-1] * len(tmp) for i in range(1, len(heap)): heap[i] = tmp[i] s = i p = i // 2 while s >= 2 and heap[p] > heap[s]:
heap[p], heap[s] = heap[s], heap[p]
s = p
p = s // 2
for i in range(1, len(tmp)):
tmp[i] = heap[i]