排序算法学习（python版本）之堆排序（HeapSort）
Contains:堆排序以及堆排序的应用
堆排序（Heapsort）是指利用堆積這種資料結構所設計的一種排序算法。堆積是一個近似完滿二元樹的結構，並同時滿足堆積的性質：即子結點的键值或索引總是小於（或者大於）它的父節點。
[*]最差时间复杂度：O(nlogn)
[*]最优时间复杂度：O(nlogn)
[*]平均时间复杂度：O(nlogn)
建立堆，保持最大堆，堆排序（顶端最大元素与最后一个元素不断的交换）——整个过程。
#-*-coding:utf-8-*-
def heap_sort(lst):
for start in range((len(lst)-2)/2, -1, -1):
siftdown(lst,start,len(lst)-1)
for end in range(len(lst)-1, 0, -1):
lst, lst = lst, lst
siftdown(lst, 0, end - 1)
return lst
def siftdown(lst, start, end):
root = start
while True:
child = 2*root + 1
if child > end:break
if child+1<=end and lst < lst:
child += 1
if lst > lst:
lst,lst = lst,lst
root=child
else:
break
def main():
l=
print heap_sort(l)
if __name__ == '__main__':
main()
使用heapq
#!/usr/bin/env python
#-*-encoding:utf-8-*-
from heapq import heappush,heappop
def heap_sort(iterable):
h = []
for value in iterable:
heappush(h, value)
return
def main():
L =
print heap_sort(L)
if __name__ == "__main__":
main()
参考资料：
http://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F
http://blog.csdn.net/v_july_v/article/details/6198644
http://docs.python.org/2/library/heapq.html
http://rosettacode.org/wiki/Sorting_algorithms/Heapsort
http://en.wikipedia.org/wiki/Heapsort
页:
[1]