Python天天美味(32)
1. 选择排序选择排序原理是先选出最小的数，与第一个数交换，然后从第二个数开始再选择最小的数与第二个数交换，……
def selection_sort(data):
for i in range(len(data) - 1):
min = data
k = i
for j in range(i, len(data)):
if data < min:
min = data
k = j
if ik:
data, data = data, data
2. 堆排序
堆排序的原理将数组调整成堆，然后将堆顶元素与最后一个元素交换，然后将最后一个节点剔除出堆，再将剩下的数组调整成堆，然后再交换堆顶元素与最后一个元素……
def heap_adjust(data, s, m):
if 2 * s > m:
return
temp = s - 1
if data > data:
temp = 2 * s - 1
if 2 * sdata:
temp = 2 * s
if temps - 1:
data, data = data, data
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, data[-1] = data[-1], data
for n in range(len(data) - 1, 1, -1):
heap_adjust(data, 1, n)
data, data = data, data
3. 效率
堆排序的效率还是蛮高的，结果如下：
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详解
页:
[1]