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]
- 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
来源: http://www.phpxs.com/code/1004977/