| 时间复杂度（最好） | 时间复杂度（最坏） | 时间复杂度（平均） | 空间复杂度 | 稳定性 | ||
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 | |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 | |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 | |
| 快速排序 | O(nlog(n)) | O(n^2) | O(nlog(n)) | O(nlog(n)) | 不稳定 | |
| 归并排序 | O(nlog(n)) | O(nlog(n)) | O(nlog(n)) | O(n) | 稳定 |
1、选择排序
选择排序：选择最大/最小的数字，与未排好序的数组部分最前面的数字进行交换。
def select_sort(data):
for i in range(len(data)-1):
min_index = i
for j in range(i+1,len(data)):
if data[min_index]>data[j]:
min_index = j
data[min_index],data[i] = data[i],data[min_index]
return data
2、插入排序
插入排序：遍历n个数字，对于第i个数字，在0到i之间找到它的适合位置，替换进去。
def insert_sort(data):
for i in range(len(data)):
j = i
while j>0:
if data[j]<data[j-1]:
data[j-1],data[j] = data[j],data[j-1]
j -= 1
return data
3、冒泡排序
冒泡排序：反复对相邻的两个数字两两比较，从而将较大的数字排到后面去。
def bubble_sort(data):
for i in range(len(data)-1):
for j in range(len(data)-i-1):
if data[j]>data[j+1]:
data[j],data[j+1] = data[j+1],data[j]
return data
4、快速排序
快速排序：它选择一个基准值，将待排序数组分割成比基准值大的和比基准值小的两部分，对两部分再次选择基准值进行分割，最终完成排序。
def quick_sort(data):
if len(data)<2:
return data
base = data[0]
left = [i for i in data[1:] if i<=base]
right = [i for i in data[1:] if i>base]
return quick_sort(left) + [base] +quick_sort(right)
5、归并排序
归并排序：将原数组分割成二项子集，分别对各个子集进行排序。接着将两两二项子集进行合并，重复多次直至将整个数组合并回来。
def merge_sort(data):
if len(data)<2:
return data
middle = len(data)//2
left = merge_sort(data[:middle])
right = merge_sort(data[middle:])
return merge(left, right)
def merge(left, right):
res = []
left_index = right_index = 0
while left_index<len(left) and right_index<len(right):
if left[left_index]<right[right_index]:
res.append(left[left_index])
left_index += 1
else:
res.append(right[right_index])
right_index += 1
if left_index==len(left):
for i in right[right_index:]:
res.append(i)
if right_index == len(right):
for i in left[left_index:]:
res.append(i)
return res
原文：https://www.cnblogs.com/stacey999999/p/12073276.html