算法学习笔记–排序之选择排序
定义
选择排序需要额外的存储空间，且排序的时间为O(N^2),其实为O(1/2(N^2))但是常数可以省略。 选择排序每次都遍历一遍剩下的数，然后选出最小的一个数放到排序好的存储空间中去。
实现
python中没有数组，所以用列表(List)代替。
def find_smallest(array):
smallest = array[
0]
for i
in range(len(array)):
if smallest > array[i]:
smallest = array[i]
return smallest
def selection_sort(array):
sorted = []
for n
in range(len(array)):
smallest = find_smallest(array)
sorted.append(smallest)
array.remove(smallest)
return sorted
if __name__ ==
'__main__':
list1 = [
4,
3,
2,
1,-
2,
3,
5,
3]
print list1
print selection_sort(list1)
运行结果
[-
2,
1,
2,
3,
3,
3,
4,
5]
