使用场景：
1，空间复杂度 越低越好、n值较大：
堆排序 O(nlog2n) O(1)
2，无空间复杂度要求、n值较大：
桶排序 O(n+k) O(n+k)
经典排序算法图解：
经典排序算法的复杂度：
大类一（比较排序法）：
1、冒泡排序（Bubble Sort）【前后比较-交换】
python代码实现：
d0 = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 2, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44]
d0_out = [2, 2, 2, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 9, 12, 15, 44, 45, 54, 64] # 正确排序 while 1:
state = 0 # 假设本次循环没有改变
for i in range(len(d0) - 1):
if d0[i] > d0[i + 1]:
d0[i], d0[i + 1] = d0[i + 1], d0[i]
state = 1 # 有数值交换，那么状态值置1
if not state: # 如果没有数值交换，那么就跳出
break print(d0)
print(d0_out)
2、选择排序（Selection Sort）【选择最小的数据放在前面】
python代码实现：
def select_sort(data):
d1 = []
while len(data):
min = [0, data[0]]
for i in range(len(data)):
if min[1] > data[i]:
min = [i, data[i]]
del data[min[0]] # 找到剩余部分的最小值，并且从原数组中删除
d1.append(min[1]) # 在新数组中添加
return d1 if __name__ == "__main__":
d0 = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 2, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44] # 原始乱序
d0_out = [2, 2, 2, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 9, 12, 15, 44, 45, 54, 64] # 正确排序
d1 = select_sort(d0)
print(d1)
print(d0_out)
3、插入排序（Insertion Sort）【逐个插入到前面的有序数中】
直接插入排序-python实现：
def direct_insertion_sort(d): # 直接插入排序，因为要用到后面的希尔排序，所以转成function
d1 = [d[0]]
for i in d[1:]:
state = 1
for j in range(len(d1) - 1, -1, -1):
if i >= d1[j]:
d1.insert(j + 1, i) # 将元素插入数组
state = 0
break
if state:
d1.insert(0, i)
return d1 if __name__ == "__main__":
d0 = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 2, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44] # 原始乱序
d0_out = [2, 2, 2, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 9, 12, 15, 44, 45, 54, 64] # 正确排序
d1 = direct_insertion_sort(d0)
print(d1)
print(d0_out)
折半插入排序-python实现：
d0 = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 2, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44] # 原始乱序
d0_out = [2, 2, 2, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 9, 12, 15, 44, 45, 54, 64] # 正确排序 d1 = [d0[0]]
del d0[0] for i in d0:
index_now = [0, len(d1)]
while 1:
index = index_now[0] + int((index_now[1] - index_now[0]) / 2)
if i == d1[index]:
d1.insert(index+1,i)
break
elif index in index_now: # 如果更新的index值在index_now中存在（也有可能是边界），那么就表明无法继续更新
d1.insert(index+1,i)
break
elif i > d1[index]:
index_now[0] = index
elif i < d1[index]:
index_now[1] = index print(d1)
print(d0_out)
4、希尔排序（Shell Sort）【从大范围到小范围进行比较-交换】类似冒泡和插入的联合
python代码实现：
def direct_insertion_sort(d): # 直接插入排序，因为要用到后面的希尔排序，所以转成function
d1 = [d[0]]
for i in d[1:]:
state = 1
for j in range(len(d1) - 1, -1, -1):
if i >= d1[j]:
d1.insert(j + 1, i) # 将元素插入数组
state = 0
break
if state:
d1.insert(0, i)
return d1 def shell_sort(d): # d 为乱序数组，l为初始增量,其中l<len(d),取为len(d)/2比较好操作。最后还是直接省略length输入
length = int(len(d) / 2) #
num = int(len(d) / length) #
while 1: for i in range(length):
d_mid = []
for j in range(num):
d_mid.append(d[i + j * length])
d_mid = direct_insertion_sort(d_mid)
for j in range(num):
d[i + j * length] = d_mid[j]
# print(d)
length = int(length / 2)
if length == 0:
return d
break
# print('length:',length)
num = int(len(d) / length) if __name__ == "__main__":
d0 = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 2, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44] # 原始乱序
d0_out = [2, 2, 2, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 9, 12, 15, 44, 45, 54, 64] # 正确排序
d1 = shell_sort(d0)
print(d1)
print(d0_out)
5、归并排序（Merge Sort）【分治法-2-4-8插入排序】
python代码实现（这个地方是由大往小进行递归）：
# 归并排序，还有些问题。其中有些细节需要重新理解
# 也是递归问题
def merge_sort(data): # 分治发的典型应用，大问题拆分成小问题，逐个击破，之后将结果合并
half_index = int(len(data) / 2) # 将数组拆分 d0 = data[:half_index]
d1 = data[half_index:] if len(d0) > 1:
d0 = merge_sort(d0) if len(d1) > 1:
d1 = merge_sort(d1) index = 0
for i in range(len(d1)):
state = 1
for j in range(index, len(d0)):
if d1[i] < d0[j]:
state = 0
index = j + 1
d0.insert(j, d1[i])
break
if state == 1: # 如果大于d0这个队列的所有值，那么直接extend所有数据
d0.extend(d1[i:])
break
return d0 if __name__ == "__main__":
d0 = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 2, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44] # 原始乱序
d0_out = [2, 2, 2, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 9, 12, 15, 44, 45, 54, 64] # 正确排序
d1 = merge_sort(d0)
print(d1)
print(d0_out)
python代码实现（由小扩展到大的子序列）：
def list_sort(d0, d1): # 基元组往大扩展
index = 0
for i in range(len(d1)): # 遍历d1数组
state = 1
for j in range(index, len(d0)): # 遍历d0数组
if d0[j] > d1[i]:
state = 0
index = j + 1
d0.insert(j, d1[i])
break
if state == 1: # 如果大于d0这个队列的所有值，那么直接extend所有数据
d0.extend(d1[i:])
break
return d0 def merge_sort(data):
d0 = [[x] for x in data]
while len(d0) != 1: # 循环条件
length = len(d0)
half = int(length/2) # 除2的整数部分
quo = length%2 # 除2的商
d0_mid = []
for i in range(half):
d0_mid.append(list_sort(d0[i*2], d0[i*2+1]))
if quo:
d0_mid.append(d0[-1])
d0 = d0_mid return d0[0] if __name__ == "__main__":
d0 = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 2, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44] # 原始乱序
d0_out = [2, 2, 2, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 9, 12, 15, 44, 45, 54, 64] # 正确排序
d1 = merge_sort(d0)
print(d1)
print(d0_out)
6、快速排序（Quick Sort）【选取一个基准值，小数在左大数在在右】
python代码实现：
# import sys
# sys.setrecursionlimit(1000000) def quick_sort(data):
d = [[], [], []]
d_pivot = data[-1] # 因为是乱序数组，所以第几个都是可以的，理论上是一样的
for i in data:
if i < d_pivot: # 小于基准值的放在前
d[0].append(i)
elif i > d_pivot: # 大于基准值的放在后
d[2].append(i)
else: # 等于基准值的放在中间
d[1].append(i) # print(d[0], d[1], d[2])
if len(d[0]) > 1: # 大于基准值的子数组，递归
d[0] = quick_sort(d[0]) if len(d[2]) > 1: # 小于基准值的子数组，递归
d[2] = quick_sort(d[2]) d[0].extend(d[1])
d[0].extend(d[2])
return d[0] if __name__ == "__main__":
d0 = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 2, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44] # 原始乱序
d0_out = [2, 2, 2, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 9, 12, 15, 44, 45, 54, 64] # 正确排序
d1 = quick_sort(d0)
print(d1)
print(d0_out)
7、堆排序（Heap Sort）【利用最大堆和最小堆的特性】
python代码实现：
d0 = [99, 5, 36, 7, 22, 17, 46, 12, 2, 19, 25, 28, 1, 92] def sort_max(data): # 直接冒泡一下吧,小到大
for i in range(len(data) - 1):
for j in range(len(data) - 1):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
return data def heap_min(data,type):
index = 0
if not type:
for i in range(len(data[1:])):
if data[index] > data[i+1]:
index = i+1
data[0],data[index] = data[index],data[0]
return data
else:
for i in range(len(data[1:])):
if data[index] < data[i+1]:
index = i+1
data[0],data[index] = data[index],data[0]
return data # d0 = [3,2,1,10,3]
# print(heap_min(d0,1))
# print(heap_min(d0,0)) import numpy as np def heap_adj(data, type): # data 原始堆，type=1最大堆，type=0最小堆
length = len(data)
floor = int(np.log2(length))
for i in range(floor, 0, -1): # 3（7 6 5 4）-2（3 2）-1（1）
for j in range(2 ** floor - 1, 2 ** (floor - i) - 1, -1):
# print(i,j) # j-1 为当前父节点
d_mid = [data[j - 1]] # j = 7,j-1 =6 index
if j * 2 <= length: #
d_mid.append(data[j * 2 - 1])
if j * 2 + 1 <= length:
d_mid.append(data[j * 2]) d_mid = heap_min(d_mid, type) if len(d_mid) == 2:
data[j - 1], data[j * 2 - 1] = d_mid[0], d_mid[1]
elif len(d_mid) == 3:
data[j - 1], data[j * 2 - 1], data[j * 2] = d_mid[0], d_mid[1], d_mid[2]
return data d1 = []
for i in range(len(d0)):
data = heap_adj(d0, 0)
d1.append(d0[0])
del d0[0] print(d1)
大类二（非比较排序法）：
8、计数排序（Counting Sort）【字典计数-还原】
python代码实现：
d0 = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 2, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44]
d0_out = [2, 2, 2, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 9, 12, 15, 44, 45, 54, 64] d_max = 0
d_min = 0
for i in d0:
if d_max<i:
d_max = i
if d_min>i:
d_min = i d1 = {}
for i in d0:
if i in d1.keys():
d1[i] += 1
else:
d1[i] = 1 d2 = []
for i in range(d_min,d_max+1):
if i in d1.keys():
for j in range(d1[i]):
d2.append(i) print(d2)
9、桶排序（Bucket Sort）【链表】
python代码实现：
d0 = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 2, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44] d1 = [[] for x in range(10)]
for i in d0:
d1[int(i/10)].append(i) # print(d1) for i in range(len(d1)):
if d1[i] != []:
d2 = [[] for x in range(10)]
for j in d1[i]:
d2[j%10].append(j)
d1[i] = d2 # print(d1) d3 = []
for i in d1:
if i:
for j in i:
if j:
for k in j:
if k:
d3.append(k)
print(d3)
10、基数排序（Radix Sort）
python代码实现：
d0 = [2, 15, 5, 9, 7, 6, 4, 12, 5, 4, 2, 64, 5, 6, 4, 2, 3, 54, 45, 4, 44] d1 = [[] for x in range(10)] # 第一次 最小位次排序
for i in d0:
d1[i % 10].append(i) print(d1) d0_1 = []
for i in d1:
if i:
for j in i:
d0_1.append(j)
print(d0_1) # 第二次 次低位排序
d2 = [[] for x in range(10)]
for i in d0_1:
d2[int(i/10)].append(i)
print(d2) d0_2 = []
for i in d2:
if i:
for j in i:
d0_2.append(j)
print(d0_2)
文末再次感谢：博主 一像素 https://www.cnblogs.com/onepixel/
参考文档出处：
十大经典排序算法（动图演示） https://www.cnblogs.com/onepixel/articles/7674659.html