堆排序法是选择排序法的一种,是对简单排序法的改进,提高了效率.

首先是对堆的介绍,堆分为大根堆和小根堆.大根堆有两个充要条件:一是必须是一棵完全二叉树;二是对于堆中任意一个非子叶节点,都满足ki不小于k2i且ki不小于k(2i+1).因此k1

是堆中最大的的,因此名为大根堆,小根堆亦是如此.

假设待排序数组为A={95,76,66,50,36,12,25,36},将其实现从小到大排列.堆的核心方法主要有以下两个步骤:

1.将数组建成一个大根堆

2.取大根堆的根,让后将剩余数组再次调整为大根堆.反复执行步骤二,直到所有元素选择完毕.

首先介绍python中实现堆的模块heapq:

heapify(A):将数组A转化为堆,默认为小根堆

heappush(A,x):向堆A中添加元素x,得到的仍是堆

heappop(A)弹出堆A中最小的元素,并且维持剩余元素的堆结构

heapreplace(A,x):弹出堆A中最小的元素,然后将新元素x插入

用python实现堆排序法,定义名为Heapsort的堆排序函数,变量如下:

nums变量:表示待排序的数组名

result变量:表示返回的排序结果列表

函数定义如下:

import heapqdef Heapsort(nums):# 将列表转换为堆结构heapq.heapify(nums)result = []# 循环直到堆为空while nums:# 移除并返回堆顶元素result.append(heapq.heappop(nums))return result

输入;

x=[13,354,23,145,75,12]
print(Heapsort(x))

输出

[12, 13, 23, 75, 145, 354]