文档章节

11.排序算法_7_堆排序

片刻
 片刻
发布于 2016/06/20 11:47
字数 301
阅读 38
收藏 0

时间复杂度是程序运行的时间,也可以说是次数;
空间复杂度是程序占用的空间;

7.堆排序

#!/usr/bin/python
# coding: utf8

def heap_sort(lst):
    def sift_down(start, end):
        """最大堆调整"""
        root = start
        while True:
            # 结点的子叶的位置
            child = 2 * root + 1
            # print root, child
            # 判断是否越界
            if child > end:
                break
            # 判断孩子结点是否是 尾结点; 如果不是,就左右子树,找出最大子结点的位置
            if child + 1 <= end and lst[child] < lst[child + 1]:
                # 该自己的坐标为右孩子的位置
                child += 1
            # print root, child, '****'
            # 如果 父结点 < 最大孩子, 就交换位置
            if lst[root] < lst[child]:
                lst[root], lst[child] = lst[child], lst[root]
                root = child
            else:
                break

    # 创建最大堆( len(lst)/2-1表示右子叶结点的位置 )
    for start in xrange(len(lst)/2-1, -1, -1):
        sift_down(start, len(lst) - 1)

    # print lst
    # 堆排序
    for end in xrange(len(lst) - 1, 0, -1):
        # print end, '--------',lst
        # 每一次堆排序找出最大值来,然后放到最后位置上
        lst[0], lst[end] = lst[end], lst[0]
        # print end, '--',lst
        sift_down(0, end - 1)
    return lst
            
def main():
    l = [9,2,1,7,6,8,5,3,4]
    heap_sort(l)
    print '结束:', l

if __name__ == "__main__":
    main()

结果:

结束: [1, 2, 3, 4, 5, 6, 7, 8, 9]
[Finished in 0.0s]

© 著作权归作者所有

片刻
粉丝 106
博文 269
码字总数 306754
作品 0
海淀
高级程序员
私信 提问
十大经典排序算法(动图演示)转

0、算法概述 0.1 算法分类 十种常见排序算法可以分为两大类: 非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。 ...

o0无忧亦无怖
2018/07/05
118
0
维基百科上的算法和数据结构链接很强大

突然发现维基百科上的算法和数据结构比百度百科强多啦,图文并茂。 其实这个网站不错:http://www.sorting-algorithms.com 冒泡排序: bubble冒泡的意思 http://zh.wikipedia.org/wiki/%E5%8...

晨曦之光
2012/03/09
2.3K
1
排序算法汇总——转载自http://blog.csdn.net/zhanglong_daniel/article/details/52513058

1. 冒泡排序 1.1 算法原理: S1:从待排序序列的起始位置开始,从前往后依次比较各个位置和其后一位置的大小并执行S2。 S2:如果当前位置的值大于其后一位置的值,就把他俩的值交换(完成一次...

biubiubiu!
2016/10/09
0
0
常用排序算法之JavaScript实现

1、插入排序 1)算法简介 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插...

开心303
2014/09/05
184
0
插入排序,希尔排序,堆排序详解

本文将介绍三种排序算法--插入排序,希尔排序,堆排序。本文所有例子都是使用升序 一.插入排序 算法思想 维护一个有序数组,将要插入的数据与有序数组自最后一个元素直到合适位置的数一一比较...

crazys_蘑菇
2018/06/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

只需一步,在Spring Boot中统一Restful API返回值格式与统一处理异常

统一返回值 在前后端分离大行其道的今天,有一个统一的返回值格式不仅能使我们的接口看起来更漂亮,而且还可以使前端可以统一处理很多东西,避免很多问题的产生。 比较通用的返回值格式如下:...

晓月寒丶
昨天
61
0
区块链应用到供应链上的好处和实际案例

区块链可以解决供应链中的很多问题,例如记录以及追踪产品。那么使用区块链应用到各产品供应链上到底有什么好处?猎头悬赏平台解优人才网小编给大家做个简单的分享: 使用区块链的最突出的优...

猎头悬赏平台
昨天
29
0
全世界到底有多少软件开发人员?

埃文斯数据公司(Evans Data Corporation) 2019 最新的统计数据(原文)显示,2018 年全球共有 2300 万软件开发人员,预计到 2019 年底这个数字将达到 2640万,到 2023 年达到 2770万。 而来自...

红薯
昨天
66
0
Go 语言基础—— 通道(channel)

通过通信来共享内存(Java是通过共享内存来通信的) 定义 func service() string {time.Sleep(time.Millisecond * 50)return "Done"}func AsyncService() chan string {retCh := mak......

刘一草
昨天
59
0
Apache Flink 零基础入门(一):基础概念解析

Apache Flink 的定义、架构及原理 Apache Flink 是一个分布式大数据处理引擎,可对有限数据流和无限数据流进行有状态或无状态的计算,能够部署在各种集群环境,对各种规模大小的数据进行快速...

Vincent-Duan
昨天
62
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部