堆排序
堆排序（Heapsort）就是指运用堆这类算法设计所设计方案的一种快速排序算法。沉积是一个类似完全二叉树的构造，并另外考虑沉积的特性：即子节点的键值或数据库索引一直低于（或是超过）它的父节点。堆排序能够说成一种运用堆的定义来排列的选择排序。分成二种方式：
- 大顶堆：每一个连接点的值都大于或等于他的儿子连接点的值，在堆排序算法中用以升序排序；
- 小顶堆：每一个连接点的值都小于或等于他的儿子连接点的值，在堆排序算法中用以降序排序；
堆排序的均值算法复杂度为 Ο(nlogn)。
优化算法流程
- 建立一个堆 H[0……n-1]；
- 把堆首（最高值）和堆尾交换；
- 把堆的规格变小 1，并启用 shift_down(0)，目地是把新的二维数组顶部数据信息调节到相对部位；
- 反复流程 2，直至堆的规格为 1。
Python 编码完成
def buildMaxHeap(arr):
import math
for i in range(math.floor(len(arr)/2),-1,-1):
heapify(arr,i)
def heapify(arr, i):
left = 2*i 1
right = 2*i 2
largest = i
if left < arrLen and arr[left] > arr[largest]:
largest = left
if right < arrLen and arr[right] > arr[largest]:
largest = right
if largest != i:
swap(arr, i, largest)
heapify(arr, largest)
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def heapSort(arr):
global arrLen
arrLen = len(arr)
buildMaxHeap(arr)
for i in range(len(arr)-1,0,-1):
swap(arr,0,i)
arrLen -=1
heapify(arr, 0)
return arr
