python 排序算法

 1 #coding:utf-8
 2 ‘‘‘
 3 比较相邻的元素，每一趟交换后，最后的元素是最大的。
 4 第一次比较n-1次，第二次比较n-2次。。。第n-1次比较1次
 5 进行n-1次冒泡次数
 6 最优时间复杂度O(n),最坏时间复杂度O(n^2)
 7 ‘‘‘
 8 
 9 def bubble_sort(b_list):
10     n = len(b_list)
11     for j in range(0, n-1):
12         count = 0
13         for i in range(0, n-1-j):
14             if b_list[i] > b_list[i+1]:
15                 count += 1
16                 t = b_list[i+1]
17                 b_list[i+1] = b_list[i]
18                 b_list[i] = t
19         if count == 0:
20             break

 1 #coding:utf-8
 2 ‘‘‘
 3 找到最小的放到最前面，接着从剩余的继续找最小的，放到第二个。
 4 一共找n-1次，最优O(n),最坏O(n^2)
 5 ‘‘‘
 6 
 7 def select_sort(s_list):
 8     n = len(s_list)
 9     for j in range(0, n-1):
10         min_v = j
11         for i in range(j+1, n):
12             if s_list[i] < s_list[min_v]:
13                 min_v = i
14         t = s_list[j]
15         s_list[j] = s_list[min_v]
16         s_list[min_v] = t

 1 #coding:utf-8
 2 ‘‘‘
 3 从第二个开始 和前面的有序序列比较，比较大小插进去
 4 最优O(n),最坏O(n^2)
 5 ‘‘‘
 6 
 7 def insert_sort(i_list):
 8     n = len(i_list)
 9     for j in range(1, n):
10         i = j
11         while i > 0:
12             if i_list[i] < i_list[i-1]:
13                 t = i_list[i]
14                 i_list[i] = i_list[i-1]
15                 i_list[i-1] = t
16                 i = i - 1
17             else:
18                 break