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 ]
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 ]
2. 堆排序
堆排序的原理将数组调整成堆，然后将堆顶元素与最后一个元素交换，然后将最后一个节点剔除出堆，再将剩下的数组调整成堆，然后再交换堆顶元素与最后一个元素……
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 ]
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 ]
3. 效率
堆排序的效率还是蛮高的，结果如下：
selection_sort
0:00:02.219000
heap_sort 0:00:00.157000
heap_sort 0:00:00.157000
Python 天天美味系列（总）
Python 天天美味(30) - python数据结构与算法之快速排序
Python 天天美味(31) - python数据结构与算法之插入排序
Python 天天美味(32) - python数据结构与算法之堆排序
Python 天天美味(33) - 五分钟理解元类（Metaclasses）[转]
Python 天天美味(34) - Decorators详解
本文转自CoderZh博客园博客，原文链接：http://www.cnblogs.com/coderzh/archive/2008/09/22/1296195.html，如需转载请自行联系原作者
