Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说十大排序算法（五）--- 堆排序,希望能够帮助你!!!。

十大排序算法（五）--- 堆排序

理解堆排序需要首先了解堆的特性，不熟悉的朋友可以参考我之前的文章《数据结构-堆》。堆排序就是利用堆这种数据结构的特性进行排序的算法。分为两种：1. 升序排序，使用最大堆或者叫大顶堆。2. 降序排序，使用最小堆或者叫小顶堆。

堆排序的步骤如下：

1. 创建一个堆Heap[n]。
2. 把堆顶(也就是根节点)元素与堆尾元素进行互换。
3. 把堆的尺寸缩小1(此时最后一个元素已经排好，下次操作不再参与排序)， 并向下调整堆顶元素，将其调整到合适的位置。
4. 重复#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解释器执行一下，会输出如下结果：

可以看到，排序正确。

今天的分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。