文章 > Python基础教程 > python堆排序是什么?

python堆排序是什么?

头像

小妮浅浅

2021-03-05 17:18:16669浏览 · 0收藏 · 0评论

1、概念

堆排序是高效排序算法的另一个例子,它的主要优点是,无论输入数据如何,它的最坏情况运行时间都是O(n*logn)。

顾名思义,堆排序在很大程度上取决于堆数据结构的常见实现——优先级队列。

毫无疑问,堆排序是一种简单的排序算法,与其他简单的实现相比,堆排序更有效、更常见。

2、工作原理

是从堆逐个“移除”元素并将它们添加到已排序的数组里,在进一步解释和重新访问堆数据结构之前,我们应该了解堆排序本身的一些属性。

它是一种原地算法(译者注:in-place algorithm,多数翻译为“原地算法”,少数也翻译为“就地算法”。这种算法是使用小的、固定数量的额外内存空间来转换资料的算法。),意味着它需要恒定数量的内存,即所需内存不取决于初始数组本身的大小,而取决于存储该数组所需的内存。

例如,不需要原始数组的副本,也不需要递归和递归调用堆栈。最简单的堆排序实现通常使用第二个数组来存储排序后的值。我们将使用这种方法,因为它在代码中更直观、更易于实现,但它也是百分百的原地算法。

堆排序不稳定,意思是相等的值,并不会在同样的相对位次上。对于整数、字符串等这些基本类型,不会出现这类问题,但当我们对复杂类型的对象排序时,可能会遇到。

以上就是python堆排序的介绍,希望能对大家有所帮助。更多Python学习指路:python基础教程

关注公众号

关注公众号,随时随地在线学习

本教程部分素材来源于网络,版权问题联系站长!

底部广告图 底部广告图按钮