python 排序

最近连冒泡都忘记咋写了，真是想找个缝了钻进去，又熟悉了一遍，做个笔记

 1 '''
 2 冒泡排序
 3 相邻的二个元素比较，大的放在后面
 4 时间复杂度 O（n^2）
 5 空间复杂度 O（1）
 6 '''
 7 def bubble_sort(array)->list:
 8     for i in range(len(array)):
 9         for j in range(len(array)-1):
10             if array[j] > array[j+1]:
11                 array[j],array[j+1] = array[j+1],array[j]
12     return array
13 
14 '''
15 快速排序 
16 选择一个基准值，将所有比他大的放在另一边，然后迭代,最后剩下长度1会结束循环
17 时间复杂度 O（nlog2n）
18 空间复杂度 O（log2n）
19 '''
20 def quick_sort(array)->list:
21     if len(array) <=1:return array
22     else:
23         mid = array[0]
24         litt = [x for x in array[1:] if x < mid]
25         big = [x for x in array[1:] if x >= mid]
26         return quick_sort(litt) + [mid] +quick_sort(big)
27 
28 '''
29 选择排序
30 将前面的数与后面的数依次对比，然后大小互换
31 时间复杂度 O（n^2）
32 空间复杂度 O（1）
33 '''
34 def select_sort(array):
35     for i in range(len(array)-1):
36         for j in range(i+1,len(array)):
37             if array[i] > array[j]:array[i],array[j]=array[j],array[i]
38     return array
39 
40 
41 
42 '''
43 插入排序
44 每次取一个值，与左边对比，小的放在左边
45 时间复杂度 O（n^2）
46 空间复杂度 O（1）
47 '''
48 def insert_sort(array):
49     for i in range(1,len(array)):
50         temp = array[i]
51         j = i-1
52         while(j>=0 and array[j]>temp):
53             array[j+1] = array[j]
54             array[j] = temp
55             j -= 1
56     return array
57 
58 l = [3,4,2,1]
59 print(insert_sort(l))

参考博客：

https://www.cnblogs.com/ladder/p/10685051.html

https://blog.csdn.net/ITmincherry/article/details/100124008

https://zhuanlan.zhihu.com/p/83148834