Python天天美味(32) - python数据结构与算法之堆排序

1. 选择排序

选择排序原理是先选出最小的数,与第一个数交换,然后从第二个数开始再选择最小的数与第二个数交换,……

def selection_sort(data):     for i in range(len(data) - 1):         min = data[i]         k = i         for j in range(i, len(data)):             if data[j] < min:                 min = data[j]                 k = j         if i <> k:             data[i], data[k] = data[k], data[i]
  1. 堆排序

堆排序的原理将数组调整成堆,然后将堆顶元素与最后一个元素交换,然后将最后一个节点剔除出堆,再将剩下的数组调整成堆,然后再交换堆顶元素与最后一个元素……

def heap_adjust(data, s, m):     if 2 * s > m:         return     temp = s - 1     if data[2*s - 1] > data[temp]:         temp = 2 * s - 1     if 2 * s <= m - 1 and data[2*s] > data[temp]:         temp = 2 * s     if temp <> s - 1:         data[s - 1], data[temp] = data[temp], data[s - 1]         heap_adjust(data, temp + 1, m) def heap_sort(data):     m = len(data) / 2     for i in range(m, 0, -1):         heap_adjust(data, i, len(data))     data[0], data[-1] = data[-1], data[0]     for n in range(len(data) - 1, 1, -1):         heap_adjust(data, 1, n)         data[0], data[n - 1] = data[n - 1], data[0]
  1. 效率

堆排序的效率还是蛮高的,结果如下:

selection_sort 0:00:02.219000 heap_sort 0:00:00.157000

 

Python 天天美味系列(总)

Python 天天美味(30) - python数据结构与算法之快速排序 

Python 天天美味(31) - python数据结构与算法之插入排序 

Python 天天美味(32) - python数据结构与算法之堆排序 

Python 天天美味(33) - 五分钟理解元类(Metaclasses)[转]

Python 天天美味(34) - Decorators详解

[温馨提示]:该文章由原博客园导入而来,如排版效果不佳,请移步:http://www.cnblogs.com/coderzh/archive/2008/09/22/1296195.html

微信扫一扫交流

作者:CoderZh
微信关注:hacker-thinking (一个程序员的思考)
本文出处:https://blog.coderzh.com/2008/09/22/1296195/
文章版权归本人所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。