python实现的堆排序算法代码
def heapSort(a): def sift(start, count): root = start while root * 2 + 1 < count: child = root * 2 + 1 if child < count - 1 and a[child] < a[child + 1]: child += 1 if a[root] < a[child]: a[root], a[child] = a[child], a[root] root = child else: return count = len(a) start = count / 2 - 1 end = count - 1 while start >= 0: sift(start, count) start -= 1 while end > 0: a[end], a[0] = a[0], a[end] sift(0, end) end -= 1 a = [-8,0,1,3,11,35,68] heapSort(a) print a # [-8, 0, 1, 3, 11, 35, 68]
Recursive sift(and more readable IMHO) Version:
def heapsort(a): def swap(a,i,j): tmp = a[i] a[i] = a[j] a[j] = tmp def siftdown(a, i, size): l = 2*i+1 r = 2*i+2 largest = i if l <= size-1 and a[l] > a[i]: largest = l if r <= size-1 and a[r] > a[largest]: largest = r if largest != i: swap(a, i, largest) siftdown(a, largest, size) def heapify(a, size): p = (size/2)-1 while p>=0: siftdown(a, p, size) p -= 1 size = len(a) heapify(a, size) end = size-1 while(end > 0): swap(a, 0, end) siftdown(a, 0, end) end -= 1