请选择 进入手机版 | 继续访问电脑版

[python] Python实现堆排序案例详解

[复制链接]
查看122 | 回复9 | 2021-9-13 11:49:35 | 显示全部楼层 |阅读模式

Python实现堆排序

一、堆排序简介

堆排序(Heap Sort)是利用 堆这种数据布局 所计划 的一种排序算法。

堆的布局 是一棵完全二叉树的布局 ,并且满足 堆积的性子 :每个节点(叶节点除外)的值都大于等于(或都小于等于)它的子节点。

关于二叉树和完全二叉树的先容 可以参考:https://www.jb51.net/article/222487.htm

堆排序先按从上到下、从左到右的次序 将待排序列表中的元素构造成一棵完全二叉树,然后对完全二叉树举行 调整,使其满足 堆积的性子 :每个节点(叶节点除外)的值都大于等于(或都小于等于)它的子节点。构建出堆后,将堆顶与堆尾举行 交换,然后将堆尾从堆中取出来,取出来的数据就是最大(或最小)的数据。重复构建堆并将堆顶和堆尾举行 交换,取出堆尾的数据,直到堆中的数据全部被取出,列表排序完成。

堆布局 分为大顶堆和小顶堆:

1. 大顶堆:每个节点(叶节点除外)的值都大于等于其子节点的值,根节点的值是全部 节点中最大的,以是 叫大顶堆,在堆排序算法中用于升序分列 。

2. 小顶堆:每个节点(叶节点除外)的值都小于等于其子节点的值,根节点的值是全部 节点中最小的,以是 叫小顶堆,在堆排序算法中用于降序分列 。

二、堆排序原理

堆排序的原理如下:

1. 将待排序列表中的数据按从上到下、从左到右的次序 构造成一棵完全二叉树。

2. 将完全二叉树中每个节点(叶节点除外)的值与其子节点(子节点有一个或两个)中较大的值举行 比较,假如 节点的值小于子节点的值,则交换他们的位置(大顶堆,小顶堆反之)。

3. 将节点与子节点举行 交换后,要继续比较子节点与孙节点的值,直到不必要 交换或子节点是叶节点时克制 。比较完全部 的非叶节点后,即可构建出堆布局 。

4. 将数据构造成堆布局 后,将堆顶与堆尾交换,然后将堆尾从堆中取出来,添加到已排序序列中,完成一轮堆排序,堆中的数据个数减1。

5. 重复步骤2,3,4,直到堆中的数据全部被取出,列表排序完成。

以列表 [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] 举行 升序分列 为例。列表的初始状态如下图。

Python实现堆排序案例详解

要举行 升序排序,则构造堆布局 时,利用 大顶堆。

1. 将待排序列表中的数据按从上到下、从左到右的次序 构造成一棵完全二叉树。

Python实现堆排序案例详解

2. 从完全二叉树的末了 一个非叶节点开始,将它的值与其子节点中较大的值举行 比较,假如 值小于子节点则交换。24是末了 一个非叶子节点,它只有一个子节点21,24大于21,不必要 交换。

Python实现堆排序案例详解

3. 继续将倒数第二个非叶节点的值与其子节点中较大的值举行 比较,假如 值小于子节点则交换。节点30有两个子节点5和36,较大的是36,30小于36,交换位置。

Python实现堆排序案例详解

4. 重复对下一个节点举行 比较。7小于45,交换位置。

Python实现堆排序案例详解

5. 继续重复,50大于27,不必要 交换位置。假如 不必要 举行 交换,则不用再比较子节点与孙节点。

Python实现堆排序案例详解

6. 继续重复,17小于45,交换位置。

Python实现堆排序案例详解

7. 17和45交换位置之后,17交换到了子节点的位置,还必要 继续将其与孙节点举行 比较。17大于15,不必要 交换。

Python实现堆排序案例详解

8. 继续对下一个节点举行 比较,10小于50,交换位置。

Python实现堆排序案例详解

9. 10和50交换位置之后,10交换到了子节点的位置,还必要 继续将其与孙节点举行 比较。10小于于27,交换位置。

Python实现堆排序案例详解

10. 此时,一个大顶堆构造完成,满足 了堆积的性子 :每个节点(叶节点除外)的值都大于等于它的子节点。

Python实现堆排序案例详解

11. 大顶堆构建完成后,将堆顶与堆尾交换位置,然后将堆尾从堆中取出。将50和21交换位置,交换后21到了堆顶,50(最大的数据)到了堆尾,然后将50从堆中取出。

Python实现堆排序案例详解

12. 将50从堆中取出后,找到了待排序列表中的最大值,50添加到已排序序列中,第一轮堆排序完成,堆中的元素个数减1。

Python实现堆排序案例详解

13. 取出最大数据后,重复将完全二叉树构建成大顶堆,交换堆顶和堆尾,取出堆尾。如许 每次都是取出当前堆中最大的数据,添加到已排序序列中,直到堆中的数据全部被取出。

Python实现堆排序案例详解

14. 循环举行 n 轮堆排序之后,列表排序完成。排序效果 如下图。

Python实现堆排序案例详解

三、Python实现堆排序

  1. # coding=utf-8
  2. def heap_sort(array):
  3. first = len(array) // 2 - 1
  4. for start in range(first, -1, -1):
  5. # 从下到上,从右到左对每个非叶节点进行调整,循环构建成大顶堆
  6. big_heap(array, start, len(array) - 1)
  7. for end in range(len(array) - 1, 0, -1):
  8. # 交换堆顶和堆尾的数据
  9. array[0], array[end] = array[end], array[0]
  10. # 重新调整完全二叉树,构造成大顶堆
  11. big_heap(array, 0, end - 1)
  12. return array
  13. def big_heap(array, start, end):
  14. root = start
  15. # 左孩子的索引
  16. child = root * 2 + 1
  17. while child <= end:
  18. # 节点有右子节点,并且右子节点的值大于左子节点,则将child变为右子节点的索引
  19. if child + 1 <= end and array[child] < array[child + 1]:
  20. child += 1
  21. if array[root] < array[child]:
  22. # 交换节点与子节点中较大者的值
  23. array[root], array[child] = array[child], array[root]
  24. # 交换值后,如果存在孙节点,则将root设置为子节点,继续与孙节点进行比较
  25. root = child
  26. child = root * 2 + 1
  27. else:
  28. break
  29. if __name__ == '__main__':
  30. array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
  31. print(heap_sort(array))
复制代码

运行效果 :

  1. [5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]
复制代码

代码中,先实现一个big_heap(array, start, end)函数,用于比较节点与其子节点中的较大者,假如 值小于子节点的值则举行 交换。代码中不必要 真正将数据都添加到完全二叉树中,而是根据待排序列表中的数据索引来得到节点与子节点的位置关系。完全二叉树中,节点的索引为i,则它的左子节点的索引为2*i+1,右子节点的索引为2*i+2,有n个节点的完全二叉树中,非叶子节点有n//2个,列表的索引从0开始,以是 索引为0~n//2-1的数据为非叶子节点。

实现堆排序函数heap_sort(array)时,先调用big_heap(array, start, end)函数循环对非叶子节点举行 调整,构造大顶堆,然后将堆顶和堆尾交换,将堆尾从堆中取出,添加到已排序序列中,完成一轮堆排序。然后循环构建大顶堆,每次将最大的元素取出,直到堆中的数据全部被取出。

四、堆排序的时间复杂度和稳固 性

1. 时间复杂度

在堆排序中,构建一次大顶堆可以取出一个元素,完成一轮堆排序,一共必要 举行 n轮堆排序。每次构建大顶堆时,必要 举行 的比较和交换次数匀称 为logn(第一轮构建堆时步骤多,后面重修 堆时步骤会少很多)。时间复杂度为 T(n)=nlogn ,再乘每次操作的步骤数(常数,不影响大O记法),以是 堆排序的时间复杂度为 O(nlogn) 。

2. 稳固 性

在堆排序中,会交换节点与子节点,假如 有相称 的数据,大概 会改变相称 数据的相对次序。以是 堆排序是一种不稳固 的排序算法。

到此这篇关于Python实现堆排序案例详解的文章就先容 到这了,更多相干 Python实现堆排序内容请搜索 脚本之家从前 的文章或继续欣赏 下面的相干 文章渴望 大家以后多多支持脚本之家!


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

avatar 123457150 | 2021-9-13 14:31:29 | 显示全部楼层
东方不败还是灭绝师太啊?
回复

使用道具 举报

avatar 山东美家环保 | 2021-9-20 04:53:09 | 显示全部楼层
admin楼主,我告诉你一个你不知道的的秘密,有一个牛逼的网站,他卖的服务器是永久的,我们的网站用 服务器都是在这家买的,你可以去试试。访问地址:http://fwq.mxswl.com
回复

使用道具 举报

avatar 浪子孤女 | 2021-9-21 10:04:30 | 显示全部楼层
看了这么多帖子,第一次看到这么高质量内容!
回复

使用道具 举报

avatar Creseda | 2021-9-27 01:35:57 | 显示全部楼层
有内涵!
回复

使用道具 举报

avatar 陈陈430 | 2021-9-30 21:42:35 | 显示全部楼层
哥回复的不是帖子,是寂寞!
回复

使用道具 举报

avatar 123457390 | 2021-10-6 07:14:50 | 显示全部楼层
有钱、有房、有车,人人都想!
回复

使用道具 举报

avatar 123457462 | 2021-10-7 14:15:46 | 显示全部楼层
admin楼主好聪明啊!
回复

使用道具 举报

avatar 123457439 | 前天 13:24 | 显示全部楼层
好东西,学习学习!
回复

使用道具 举报

avatar 迟到399 | 半小时前 | 显示全部楼层
雷锋做好事不留名,都写在帖子里!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则