python 堆排序算法
2023-06-13 09:16:16 时间
老高最近在准备面试,正好复习到堆排序,正好总结一下
堆排序的算法思路基本如下:
- 找到最后一个非叶子节点,进行第一次循环比较,找到第一个最值
- 将找到的最值移动到末尾,长度-1,root=0,继续排序n-1次
- 每次发生比较后需要在此循环比较,直到没有发生移动或者超过最大长度
- 比较的时间复杂度O(lgn),生成堆的时间复杂度为O(n),所以总的时间复杂度为O(nlgn)
- 堆排序是不稳定的排序
def build_heap(l):
l_len = len(l)
for i in range((l_len - 2) // 2, -1, -1):
re_heap(l, l_len, i)
def build_heap_min(l):
l_len = len(l)
for i in range((l_len - 2) // 2, -1, -1):
re_heap_min(l, l_len, i)
def re_heap(h, size, root):
larger = root
left = root * 2 + 1
right = left + 1
if left < size and h[left] > h[larger]:
larger = left
if right < size and h[right] > h[larger]:
larger = right
if larger != root:
# need change
h[larger], h[root] = h[root], h[larger]
# continue
re_heap(h, size, larger)
def re_heap_min(h, size, root):
min = root
left = root * 2 + 1
right = left + 1
if left < size and h[left] < h[min]:
min = left
if right < size and h[right] < h[min]:
min = right
if min != root:
# need change
h[min], h[root] = h[root], h[min]
# continue
re_heap_min(h, size, min)
def heap_sort(l):
build_heap(l)
l_len = len(l)
for i in range(l_len - 1, -1, -1):
l[0], l[i] = l[i], l[0]
re_heap(l, i, 0)
return l
def heap_sort_min(l):
build_heap_min(l)
l_len = len(l)
for i in range(l_len - 1, -1, -1):
l[0], l[i] = l[i], l[0]
re_heap_min(l, i, 0)
return l
if __name__ == '__main__':
l = [4, 5, 6, 34, 67, 475, 545, 567, 3454]
print heap_sort(l)
print '-' * 36
print heap_sort_min(l)
相关文章
- Python笔记 第三章
- python 生成数组_Python创建数组「建议收藏」
- aic准则python_Python数据科学:线性回归
- Python ---- 算法入门(1)贪心算法解决部分背包问题
- Python爬虫:让“蜘蛛”帮我们工作
- Textmate调试Python「建议收藏」
- Python算法-查找
- python chr()和ord()_Python函数ord
- 二分查找算法的实现(Python)
- Python 3.7.0软件下载和安装教程
- 【说站】Python数据标准化是什么
- python输出unicode编码_Python以utf8编码读取文件
- python的内置函数(十一)、range()
- 数据结构与算法Python_数据结构与算法python语言实现
- Python win32api_python api文档
- 【4】python读写文件操作---详细讲解!
- Python列表常用的函数和方法(1)_Python自学第二十节
- Python 操作SQLite数据库
- python 同一秒内调用接口如何避免重复操作
- Python center()字符串居中对齐方法详解
- Python简易操作MySQL数据库指南(python操作mysql数据库)
- 安装Python MySQL驱动之快速指南(python安装mysql驱动)
- MySQL与Python的协同运行:一种全新的开发体验(mysql与python)
- Python标准库与第三方库详解
- 跟老齐学Python之有容乃大的list(2)