设为首页 收藏本站
云服务器等爆品抢先购,低至4.2元/月
查看: 723|回复: 0

[经验分享] Python实现的堆排序

[复制链接]

尚未签到

发表于 2017-5-1 09:33:53 | 显示全部楼层 |阅读模式
  堆排序属于选择排序,它其实就是一个建立大顶堆的过程
  大顶堆:
  ki <= k2i+1 且 ki <= k2i+2; i>=0;ki>=0& ki<=n;
  堆排序相较于直接选择排序的优势在于在建堆的过程中,剩余序列元素已经部分有序,剩余部分减少交换次数,节省时间, 本人觉得也有点像冒泡排序(每一次比较后将最大值放到后面).
  它的时间复杂度为O(nlogn),空间复杂度为O(1). 不稳定
  算法思路:
  1.i 为最后结点(叶子结点) (i-1)/2或(i-2)/2为它的父结点p,其实是相等的
  2.p值小于i值, 交换p 和i
  3.p值与另外一个子结点比较,若 p值较小,再交换
  4. p= p-1,i = 2* p + 1,重复2-4
  5. 若p<0,结束循环

import util
class HeapSort:
def sort(self,arrData):
for i in range(0,len(arrData)):
self.buildMaxHeap(arrData,len(arrData) -i);
return;
#建立最大堆
def buildMaxHeap(self,arrData,length):
#最后的结点
n = length - 1;
#最后结点的父结点
pn = (n-1)//2;
while pn >=0: #父结点为为根结点后停止
#("结点[%d]=" % n,arrData[n],",父结点[%d]=" % pn,arrData[pn]);
if arrData[n] > arrData[pn]:
util.swap(arrData,n,pn);
if pn * 2 + 2 == n:
#n为右结点
if arrData[n - 1] > arrData[pn]:
util.swap(arrData,n-1,pn);
else:
#n为左结点
if n + 1 < length:
#("左结点,有右结点为",arrData[n+1]);
if arrData[n + 1] > arrData[pn]:
util.swap(arrData,n+1,pn);
#else:
#("左结点,没有右结点");
#pn设为pn的兄弟结点或父结点
pn = pn -1;
#n设为pn的子结点
n = pn * 2 +1;
#0位置为最大值
#最大值要放到后边
util.swap(arrData,0,length-1);
return;
arr = [7,2,5,3,1,8,6,100,48,38,45,20,34,67,12,23,90,58];
#[3, 1, 7, 5, 6, 8, 12, 2];
#[7,2,5,3,1,8,6,100,48,38,45,20,34,67,12,23,90,58];
print(arr);
shellSort = HeapSort();
shellSort.sort(arr);
print(arr);


class Util:  
@classmethod  
def test():  
return 0;  

def swap(arr,x,y):  
t=arr[x];  
arr[x]=arr[y];  
arr[y]=t;
def printArr(arr,len):
str ='[';
for i in range(0,len):
if i == len -1:
str = str + "%d" % arr ;
else:
str = str + "%d" % arr +", ";
str = str +"]";
print(str);

运维网声明 1、欢迎大家加入本站运维交流群:群②:261659950 群⑤:202807635 群⑦870801961 群⑧679858003
2、本站所有主题由该帖子作者发表,该帖子作者与运维网享有帖子相关版权
3、所有作品的著作权均归原作者享有,请您和我们一样尊重他人的著作权等合法权益。如果您对作品感到满意,请购买正版
4、禁止制作、复制、发布和传播具有反动、淫秽、色情、暴力、凶杀等内容的信息,一经发现立即删除。若您因此触犯法律,一切后果自负,我们对此不承担任何责任
5、所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其内容的准确性、可靠性、正当性、安全性、合法性等负责,亦不承担任何法律责任
6、所有作品仅供您个人学习、研究或欣赏,不得用于商业或者其他用途,否则,一切后果均由您自己承担,我们对此不承担任何法律责任
7、如涉及侵犯版权等问题,请您及时通知我们,我们将立即采取措施予以解决
8、联系人Email:admin@iyunv.com 网址:www.yunweiku.com

所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其承担任何法律责任,如涉及侵犯版权等问题,请您及时通知我们,我们将立即处理,联系人Email:kefu@iyunv.com,QQ:1061981298 本贴地址:https://www.yunweiku.com/thread-371496-1-1.html 上篇帖子: Python折半插入排序 下篇帖子: python基础-学习笔记
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

扫码加入运维网微信交流群X

扫码加入运维网微信交流群

扫描二维码加入运维网微信交流群,最新一手资源尽在官方微信交流群!快快加入我们吧...

扫描微信二维码查看详情

客服E-mail:kefu@iyunv.com 客服QQ:1061981298


QQ群⑦:运维网交流群⑦ QQ群⑧:运维网交流群⑧ k8s群:运维网kubernetes交流群


提醒:禁止发布任何违反国家法律、法规的言论与图片等内容;本站内容均来自个人观点与网络等信息,非本站认同之观点.


本站大部分资源是网友从网上搜集分享而来,其版权均归原作者及其网站所有,我们尊重他人的合法权益,如有内容侵犯您的合法权益,请及时与我们联系进行核实删除!



合作伙伴: 青云cloud

快速回复 返回顶部 返回列表