首页 > 代码库 > 选择排序

选择排序

选择排序:

 http://www.cnblogs.com/chineking/archive/2011/05/24/implement-sort-algorithm-with-python.html

选择排序,是对冒泡排序法的一种改进,它的时间复杂度为O(n2)。

 

原理: 每一趟在n-i+1(i=1,2,…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。
第i趟简单选择排序是指通过n-i次关键字的比较,从n-i+1个记录中选出关键字最小的记录,并和第i个记录进行交换。
共需进行i-1趟比较,直到所有记录排序完成为止。
 
Python 代码:
 1 def selection_sort(sort_list):
 2     iter_len = len(sort_list)
 3     if iter_len < 2:
 4         return sort_list
 5 
 6     for i in range(iter_len-1): # i is the index
 7         smallest = sort_list[i]
 8         location = i
 9 
10         for j in range(i, iter_len):    # j >= i
11             if sort_list[j] < smallest:    # the latter < the former
12                 smallest = sort_list[j]
13                 location = j
14         
15         if i != location:
16             sort_list[i], sort_list[location] = sort_list[location], sort_list[i]
17 
18     return sort_list

 

 

选择排序