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]
2011年11月26日 星期六
Heap Sort
訂閱:
文章 (Atom)