1. 冒泡排序
正如其名，不断地将最大/小的数冒泡上来，其时间复杂度为O(N^2)，具体实现代码如下：
def bubble_sort(my_list):
circle_num = len(my_list) - 1
for i in range(circle_num):
for j in range(circle_num - i):
if my_list[j] > my_list[j + 1]:
my_list[j], my_list[j + 1] = my_list[j + 1], my_list[j]
return my_list
2. 选择排序
与冒泡排序有些类似，使用选择排序每次都会得出当前列表中的最大值。比如有一个列表[3,2,4,1,5]，第一次会选出最大值5，随后在[3,2,4,1]中再次选择最大值4，随后在[3,2,1]中选出3......将每次选出的最大值进行组合，得到的就是排序后的结果。
def selection_sort(my_list):
for i in range(0, len(my_list) - 1):
index = i
for j in range(i + 1, len(my_list)):
if my_list[index] > my_list[j]:
index = j
my_list[i], my_list[index] = my_list[index], my_list[i]
return my_list
3. 插入排序
插入排序有些类似理扑克牌的过程。假设桌上有一堆牌，首先我们拿一张在手上（假设是3），随后再从桌上挑一张牌理到手上（假设是2），那么此时手上的牌就是[2,3]。总之，需要保证手上的牌是排过序的，这样当桌上的牌拿完时，手上的牌就是排序完的"列表"。
所以我们可以构建一个新的空数组A，从需要排列的数组中取数插入A中，其时间复杂度依旧是O(N^2)，代码如下：
def insert_sort(my_list):
for i in range(1, len(my_list)):
cur = my_list[i]
for j in range(0, i):
if my_list[i] < my_list[j]:
my_list = my_list[:i] + my_list[i+1:]
my_list.insert(j, cur)
return my_list
4. 快速排序
快速排序是很多标准库里的排序方法，其平均时间复杂度为O(N * LogN)(最差为O(N ^2))。
举一个栗子，有个列表为[33,10,15,7]，我们首先取出33并称其为基准值，随后将列表剩余元素小于33的放在其左边，大于33的放在其右边，得到列表[10,15,7,33]。
随后我们对33左边的子列表再次进行上述操作，取10为基准值，得到列表[7,10,15]，由于此时基准值左右均只有一个元素，排序完毕，得到排序完的列表[7,10,15,33]。
由于待排序的列表是无序的，所以我们无论用哪个值作为基准值理论上效果都是一样的，假设我们运气不好，恰好取了最小/大值作为基准值，如下图：
那么我们将进行O(N^2)时间的运行，如果运气好取了中值呢？
此时需要进行O(N*logN)时间的运算。
代码实现：
def quick_sort(my_list):
if len(my_list) < 2:
return my_list
else:
pivot = my_list[0]
less = [i for i in my_list[1:] if i <= pivot]
greater = [i for i in my_list[1:] if i > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
5. 归并排序
归并排序是典型的使用分治思想的排序方法，首先我们来看一下如何"并"?
给定两个已排序的数组A[1,3,5,6]和B[2,4,7,8]，要求将其合并为一个已排序的数组。
首先我们比较A[0]和B[0]，将小的数A[0]放入一个新的数组R=[1]；
接着A的指针向后移一位，B的指针保持，比较A[1]和B[0]，将B[0]放入R，R=[1,2]；
比较A[1]和B[1]，R=[1,2,3]； 比较A[2]和B[1]，R=[1,2,3,4]；比较A[2]和B[2]，R=[1,2,3,4,5]；比较A[3]和B[2]，R=[1,2,3,4,5,6]，此时A的指针已经到了最后，但B还指向B[2]的位置，这时候我们需要将B[2]后的元素全部插入R尾部，得到R=[1,2,3,4,5,6,7,8]即为归并后排序完成的列表。
具体代码如下：
def merge_sorted_array(A, B):
sorted_array = []
l = 0
r = 0
while l < len(A) and r < len(B):
if A[l] < B[r]:
sorted_array.append(A[l])
l += 1
else:
sorted_array.append(B[r])
r += 1
sorted_array += A[l:]
sorted_array += B[r:]
return sorted_array
了解了"并"后我们来看一下如何进行"分": 这就简单了，可以直接从中间二分，直到每个数组只有一个元素为止，完整的归并排序的代码如下：
class Sort:
def mergesort(self, alist):
if len(alist) <= 1:
return alist
mid = len(alist) // 2
# 分
left = self.mergesort(alist[:mid])
right = self.mergesort(alist[mid:])
# 合
return Sort._merge_sorted_array(left, right)
@staticmethod
def _merge_sorted_array(A, B):
sorted_array = []
l = 0
r = 0
while l < len(A) and r < len(B):
if A[l] < B[r]:
sorted_array.append(A[l])
l += 1
else:
sorted_array.append(B[r])
r += 1
sorted_array += A[l:]
sorted_array += B[r:]
return sorted_array
6. 希尔排序
希尔排序是使用插入排序的更高效的排序。
假定一个数组A[44，12，59，36，62，43，94，7，35，52，85]，该数组的长度为11，我们设定第一个增量值11//2=5，取A[0],A[5],A[10] (每个相隔5个距离)，然后我们仅对这三个数进行插入排序，A=[43, *, *, *, *, 44, *, *, *, *, 85]（*位置不进行任何操作）；
随后我们设定增量值为5//2=3，取A[0],A[3],A[6],A[9]排序，A=[35, 12, 7, 43, 52, 36, 62, 59, 44, 94, 85]；
最后用增量值1对序列进行插入排序，但经过前两次排序，此次排序的时间效率提高了很多，具体代码如下：
def shell_sort(my_list):
length = len(my_list)
step = length // 2
while step > 0:
for i in range(step):
list = [my_list[x] for x in range(i, length, step)]
list = insert_sort(list)
for x in range(len(list)):
my_list[x * step + i] = list[x]
step = step // 2
return my_list
