Python 堆排序

发布时间:2022-05-10 08:54:25 人气:20 作者:多测师

  原理

  堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

  步骤

  创建最大堆:将堆所有数据重新排序,使其成为最大堆

  最大堆调整:作用是保持最大堆的性质,是创建最大堆的核心子程序

  堆排序:移除位在第一个数据的根节点,并做最大堆调整的递归运算

  代码

  def heap_sort(list):

Python 堆排序

  # 创建最大堆

  for start in range((len(list) - 2) // 2, -1, -1):

  sift_down(list, start, len(list) - 1)

  # 堆排序

  for end in range(len(list) - 1, 0, -1):

  list[0], list[end] = list[end], list[0]

  sift_down(list, 0, end - 1)

  return list

  # 最大堆调整

  def sift_down(lst, start, end):

  root = start

  while True:

  child = 2 * root + 1

  if child > end:

  break

  if child + 1 <= end and lst[child] < lst[child + 1]:

  child += 1

  if lst[root] < lst[child]:

  lst[root], lst[child] = lst[child], lst[root]

  root = child

  else:

  break

  以上内容为大家介绍了Python 堆排序,希望对大家有所帮助,如果想要了解更多Python相关知识,请关注多测师。https://www.e70w.com/xwzx/


上一篇:python 快速排序
下一篇:Python 计数排序
返回列表
在线客服
联系方式

热线电话

17727591462

上班时间

周一到周五

二维码
线