搜索

对元素序列如何进行堆排序

gecimao 发表于 2019-06-16 18:24 | 查看: | 回复:

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  用小根堆排序的基本思想(用小根堆排序其排序结果是递减有序的,大根堆排序是递增有序)

  此堆为初始的无序区再将最小的记录k[1](即堆顶)和无序区的最后一个记录k[n]交换,由此得到新的无序区k[1..n-1]和有序区k[n],且满足k[1..n-1]=k[n]

  由于交换后新的根节点k[1]可能违反堆性质,故应将当前无序区k[1..n-1]调整为堆.然后再次对k[1..n-1]进行上面重复的操作.直到无序区只有一个元素为止.那么排序也就算结束了.

  5和12比较不变,9,1和3比较调换1和3的位置1,5和7比较调换1和7的位置则变成这样

  还不满足小根堆继续比较9,3和7比较替换3和7的位置3,5和1比较不用换

  还有做一道选择题,说堆是——A完全二叉树 B线性表 C二叉排序树 D平衡二叉树

  那既然堆是树形结构,怎么它又是线性表呢追答n个元素序列{k1,k2...ki...kn},当且仅当满足下列关系时称之为堆:

  堆是一个线性表是线性结构不是树形结构,只是它这样的性质刚好可以用一棵二叉树了描述所以很多地方都把它当成二叉树来看待

  小根堆排序就是根最小,然后每次都把第一个元素和当前堆的最后一个元素交换,那么最后结果肯定是有序的比如这样

  {ki1,ki2...kin,k1},那么再次调换ki这个小根堆的ki1和kin就变成这样{kin,ki2...ki1,k1},这里k1一定整个序列最大的,ki1是倒数第二大的,也就是说这两个数已经是有序的了,如此循环直到有序的数前面只剩下一个数的时候,那么最后的序列也就是排好序的

  展开全部堆排序是借助(完全二叉树)结构来存储数据的,二叉树又是存储在一维数组中的,是通过二叉树的下标性质来存取数据。

  首先,将数据存在一个数组中,通过二叉树的性质,找到最后一个分支结点,比较该结点和其孩子结点的数据大小,将最小的数据交换到该分支结点;如果有交换,并且孩子结点不是叶结点,再以该孩子结点为分支结点,与它的孩子结点比较

本文链接:http://baumseelen.com/duipaixu/588.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部