十大排序算法（五）— 堆排序
理解堆排序需要首先了解堆的特性，不熟悉的朋友可以参考我之前的文章《数据结构-堆》。堆排序就是利用堆这种数据结构的特性进行排序的算法。分为两种：1. 升序排序，使用最大堆或者叫大顶堆。2. 降序排序，使用最小堆或者叫小顶堆。
堆排序的步骤如下：
- 创建一个堆Heap[n]。
- 把堆顶(也就是根节点)元素与堆尾元素进行互换。
- 把堆的尺寸缩小1(此时最后一个元素已经排好，下次操作不再参与排序)， 并向下调整堆顶元素，将其调整到合适的位置。
- 重复#2， #3两个步骤，直到堆的大小为1。
下面一系列图展示了堆排序的过程。
堆排序在对元素逐个处理过程中需要不断的对堆进行调整，其平均时间复杂度为O(nlogn)。下面是堆排序的python代码实现。
import math
#define data array for sorting
A = [1, 6, 9, 12, 2, 7]
def heap_sorting(data, length, index):
for i in range(index, -1, -1):
right = 2*i+2
left = 2*i+1
mark = i
if right < length:
if data[i] < data[right]:
mark = right
if data[mark] < data[left]:
mark = left
data[i], data[mark] = data[mark], data[i]
data[length-1], data[0] = data[0], data[length-1]
def main():
#Ascending
length=len(A)
for i in range(length , 1, -1):
heap_sorting(A, i, math.floor(i/2 – 1 ))
print(A)
if __name__==’__main__’:
main()
将上面的代码保存到一个文本文件，后缀名修改为.py。可以用python解释器执行一下，会输出如下结果：
可以看到，排序正确。
