伪代码利用了维护堆和建立堆的部分
堆排序
HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i = A.length downto 2
exchange A[1] with A[i]
A.heap-size = A.heap-size - 1
MAX-HEAPIFY(A, 1)
建立堆
BUILD-MAX-HEAP(A)
A.heap-size = A.length
for i = int(A.length / 2) downto 1
MAX-HEAPIFY(A, i)
维护堆的性质
MAX-HEAPIFY(A, i)
l = LEFT(i)
r = RIGHT(i)
if l <= A.heap-size and A[l] > A[i]
largest = l
else largest = i
if r <= A.heap-size and A[r] > A[largest]
largest = r
if largest <> i
exchange A[i] with A[largest]
MAX-HEAPIFY(A, largest)
在建立好的堆里面,根部的元素是最大的,然后把这个最大的元素和A[n]进行替换,
剩下的节点再进一步进行维护堆的性质和建立堆,如此递归到调整完所有元素,
结束的时候可以获得排好序的数组。
HEAPSORT的复杂程度为 O(nlgn)
网友评论