注意：本篇文章只是讲所有的排序逻辑和代码实现，完全掌握还需要自己手动敲出一遍甚至多遍代码，代码中的注意的注释是比较容易疏忽的地方，本篇文章没有图片进行更直观的展示排序原理，但是做到心中有图，代码独立编写也就没有了问题
基本算法插入排序
插入排序就是遍历两次数组，一次是前面的排序好的，一个是后面未排序的，将未排序的跟排序好的进行比较，如果比它大就放在它的位置就是从大到小排序，比他小放在它的位置就是从小到大排序，所以当需要遍历完所有的已排序数组的时候是最坏的情况，时间复杂度最坏的情况为o(n^2)，最好的情况为o(n),即永远只需要遍历第一个就可以进行插入操作了
# 创建一个随机的数组作为输入
import random
test_list = [random.randomint(0,100) for i in range(10)]
# 插入排序
def insert(test_list):
# 遍历未排序的数组，因为在0坐标的位置的数组只有一个也就是已经排序完成，所以在1坐标开始
for i in range(1,len(test_list)):
# 遍历未排序的数组
for j in range(0,i):
# 进行插入操作，注意相等的情况
if test_list[i]<=test_list[j]:
test_list.insert(j,test_list.pop(i))
print('第{}次'.format(i),test_list)
test_list = [random.randint(1,100) for i in range(10)]
print(test_list)
insert(test_list)
冒泡排序
冒泡排序的原理是交换，如果存在交换，证明此时还需要排序，如果不存在交换，则循环结束，得到一个冒泡，交换就是从第一个往后进行判断，看是否满足前大后小或者前小后大的顺序逻辑，所以就是从头到尾进行判断，如果0小于1进行0和1交换，1和2比较，如果1小于2进行交换，如此往下，最后一个一定是所有数中最大的数
def bubble_sort(test_list):
# 循环i次
for i in range(len(test_list)-1,0,-1):
flog = False
# 做一次冒泡排序（进行从头到尾的依次比较）
# 注意这里j+1不会越界
for j in range(i):
if test_list[j]>test_list[j+1]:
test_list[j],test_list[j+1] = test_list[j+1],test_list[j]
flog = True
print('第{}次'.format(10-i),test_list)
if not flog:
break
test_list = [random.randint(1,100) for i in range(10)]
print(test_list)
bubble_sort(test_list)
选择排序
搞懂了冒泡排序，选择排序的逻辑就比较简单了，那就是一共有多少个就循环多少次,每次挑一个最大的或者最小的出来，这样的最终序列一定是有序的
# 选择排序
def choose_sort(test_list):
for i in range(len(test_list)-1,0,-1):
max = i
for j in range(0,i):
if test_list[j] > test_list[max]:
max = j
test_list[max],test_list[i] = test_list[i],test_list[max]
print('第{}次'.format(10-i),test_list)
test_list = [random.randint(1,100) for i in range(10)]
print(test_list)
choose_sort(test_list)
高级排序
堆排序
首先讲堆排序，因为它的逻辑和选择差不多，也是首先找个最大的或者最小的
那么如何找这个最大的，就需要堆这个数据结构，
这里把一个数组的0坐标位置插入一个0，使得数组的坐标和堆的坐标相互对应，即如图所示：
堆其实就是完全二叉树的另一个名字，只不过有大根堆小根堆的区别，大根堆就是任意节点的值大约两个子节点，所以只要把数组分成了一个大根堆，再吧大根堆的根节点“选择”出来，把堆节点和最后一个节点进行交换，然后除开这个节点，对剩下的进行造堆操作，如此循环就能得到有序的排列
那么第一步，如何造堆（把一个杂乱的数组变成一个满足大根堆的排序）
首先考虑传入参数，传入堆的根节点的坐标和未节点，造堆的逻辑就是把每个父节点跟他的较大的那一个子节点进行比较，如果父节点小于该子节点，进行交换
def heapify(root_node,end_node,test_list):
# 判断是否存在后续节点
father_node = root_node
son_node = father_node*2
while son_node<=end_node:
# 注意这里son_node+1test_list[son_node]的顺序不能调换，若调换则报错（在只有左节点没有右节点的情况）
if son_node+1<=end_node and test_list[son_node+1]>test_list[son_node]:
# 找到较大的子节点,这里需要特别注意是son_node+1<=end_node否则会在一些特殊情况排序失败
son_node +=1
# 进行比较
if test_list[father_node]
造堆完成后就是相当于选择排序一样的操作了
def heap_sort(test_list):
for i in range(len(test_list)-1,0,-1):
test_list[1],test_list[i] = test_list[i],test_list[1]
这里注意每次i-1，除开已经确定好位置的节点
heapify(1,i-1,test_list)
快速排序
快速排序的要点是随便的找一个数，一般我们会找数组的第一个数作为基准值，第一次快速排序达到左边的数字都比该基准值小，右边的数字都比基准值大的效果，这样之后将数组以该基准值为界分开，分别进行递归快速排序就能得到一个有序的数组
import random
# 方便理解的非原地版：
def quick_sort(test_list):
if len(test_list)<=1:
return test_list
key = test_list[0]
left,right = [],[]
mid = []
for i in range(0,len(test_list)):
if test_list[i]key:
right.append(test_list[i])
else:
# 注意和基准值相等的情况
mid.append(test_list[i])
quick_sort(left)
quick_sort(right)
print(left+mid+right)
return left+mid+right
test_list = [random.randint(0,100) for i in range(10)]
print(test_list)
quick_sort(test_list)
优化肯定是取消它额外的空间，这里我们通过左右指针的方式进行优化，具体的实现是通过左右指针同时对数组进行遍历，如果发现左指针的位置比基准值大，将左指针的值赋给
# optimize quick
import random
def optimize_quick_sort(left,right,test_list):
if left>=right:
return
key = test_list[left]
l,r = left,right
# 注意这里l，r对坐标进行接受，方便之后的快速排序
while l=key:
r -= 1
test_list[l]=test_list[r]
# print(test_list)
while l
归并排序
归并的含义，只要理解了怎么拆开，怎么合并就掌握了归并排序
首先分析拆开，这里还是用递归，如果是5个数，分成2，3；再分成1，1和1，2；再对1，2进行拆成1，1；如果是4个数就是2:2；然后1:1和1:1
所以递归结束的条件就是数组的长度为1的时候结束
import random
def merge_sort(test_list):
if len(test_list)<=1:
return test_list
print(test_list)
mid = len(test_list)//2
left = merge_sort(test_list[:mid])
right = merge_sort(test_list[mid:])
i,j = 0,0
result = []
怎么和，我们还是假设随机的5个数：
7 ，4 ， 1，9，2
第一次拆变成：7，4 和
1，9，2
7，4拆成了[7]和[4]
用result作为返回值，那他应该返回一个[4,7]
这里采取的办法是用i,j作为[7]和[4]的指针，遍历那个小，放到result中，被放之后+=1
所以获取到的结果为result = [4],i=0,j=1，想要返回[4,7],还需要加个[7],考虑到也有可能是被拆成[4],[7]的情况
最终的代码为
# merge sort
import random
def merge_sort(test_list):
if len(test_list)<=1:
return test_list
print(test_list)
mid = len(test_list)//2
left = merge_sort(test_list[:mid])
right = merge_sort(test_list[mid:])
i,j = 0,0
result = []
while i
此外的希尔排序和桶排序理解起来比较简单，这里不再介绍
