前言：此篇只代表我的个人对排序算法的理解，并没有对相应代码进行详细的解释，只是阐述了一下大概的思路，还望大家见谅，有错误也烦请大家指出。
1.冒泡排序 O(n*n)
def bubble_sort(li:list):
length = len(li)
for i in range(0,length-1):
flag = 1
for j in range(0,length-i-1):
if li[j] > li[j+1]:
li[j],li[j+1] = li[j+1],li[j]
flag = 0
if flag == 1:
break
冒泡排序的思想就是每一轮都将最大的元素通过两两交换的方式移动到最后方，最终完成排序。
其时间复杂度也十分好判断，典型的两层循环嵌套，即O(n*n)。
由于相互间的移动只有大于才会移动，因此相同的数之间的相对顺序并不会改变，因此冒泡排序是稳定的。
2.选择排序 O(n*n)
选择排序的思想与冒泡排序类似，不过其方法并不是逐个比较移动，而是直接将最大的元素放入最后的位置，直至排序完成。
def select_sort(li:list):
length = len(li)
for i in range(0,length):
max = li[0] # 初始化最大值
maxi = 0 # 记录初始最大值的下标
for index,key in enumerate(li[0:length-i]):
if key > max:
max = key
maxi = index # 选出部分列表钟最大的，并记录下标
li[maxi],li[length-1-i] = li[length-1-i],li[maxi] # 交换
此外，我还提供一个优化版的选择排序，即一次性排出最大值和最小值（指针法）：
def better_select_sort(li:list):
begin = 0
end = len(li)-1
while begin < end:
maxi = begin
mini = begin
max = li[begin]
min = li[begin]
for i in range(begin,end+1): # 在不断压缩的范围内找到最大值和最小值
if li[i] > max:
maxi = i
max = li[i]
if li[i] < min:
mini = i
min = li[i]
li[mini],li[begin] = li[begin],li[mini] # 交换begin和最小值
if li[maxi] == min: # 同时也应该注意最后两个数的情况，即5，4，先换成4，5，
# 如果再交换就是又变成5，4了，所有需要判断一下有没有无效的交换
maxi = mini # 纠正
li[maxi],li[end] = li[end],li[maxi]
begin+=1
end-=1 # 收缩范围这种方法即一次性选出最大和小的数然后放入到最后一个位置和第一个位置（相对），然后不断收缩范围直到有序。
这种两层循环的嵌套与冒泡排序相同是O（n*n）。
很显然，若存在两个相同的最大值存在，很显然这两个相同的最大值相对顺序会变化，因此这种排序是不稳定的。
3.插入排序 O(n*n)
这种排序方法类似我们小时候玩的扑克牌，在每得到一张牌时，我们需要整理，把这张牌放在应该放入的位置，即每一次都把数放在当前序列中正确的位置上。
def insert_sort(li:list):
length = len(li)
for i in range(0,len(li)-1):
# 一开始有一张牌，只需要对len(li)-1的牌进行插入
end = i
temp = li[end+1] # 暂存待插入值
while end >= 0:
if li[end] > temp:
# 若比待插入值大，就直接向后挪动覆盖即可，因为已经保存了待插入的值
li[end+1] = li[end]
end-=1
else: # 找到了待插入的位置，即找到了第一个比待插入值小的
break
li[end+1] = temp # 只需放在第一个比待插入值小的后方即可上述代码之意即为从第一张牌开始，依次放入该放的位置，若前一个数比待插入的数大，那么就将前一个数向后挪动，否则就是已经找到插入的位置，这里有一种特殊情况是已经找到第一个了，发现待插入的数是最小的，因此我们设计暂存临时值，最后将其插入的方法，这样就所有的情况都适合。
插入排序只有大于才会向后挪动腾出位置，因此相等的数之间的相对顺序并不会改变，因此插入排序是稳定的。
4.希尔排序（不断地进行预排序）O（n*logn）
希尔排序就是分组的插入排序，分组由组距gap决定，插入排序默认gap为1，即在gap不断缩小的过程中，希尔排序进行大组距的预排序，到gap为1时，就会对近乎有序的列表进行插入排序，但这时的插入排序在进行过预排序后，效率会很高，其中预排序的时间复杂度为O（logn），总体的时间复杂度为O（n*log2n）。
def shell_sort(li:list):
length = len(li)
gap = length
while gap > 1:
gap //= 2 # 进行分组插入排序的预排序
for i in range(0,len(li)-gap):
end = i
temp = li[end+gap]
while end >= 0:
if li[end] > temp:
li[end+gap] = li[end]
end-=gap
else:
break
li[end+gap] = temp
由于希尔排序是分组预排序，相同的最值存在于不同的组别，相对顺序会发生变化，因此希尔排序是不稳定的。
5.堆排序 O（logn*n）
堆的逻辑结构时一颗完全二叉树构成，物理结构时数组，通过父子间变换的公式来实现逻辑结构上的二叉树，堆分为大堆和小堆，大堆的所有父亲都大于等于孩子，小堆反之，对于大堆和小堆，其总根的数值一定是最大的（最小的），这一点便是堆排序的关键----向下调整算法。
根据完全二叉树的性质，除了最后一层，其余都是2*h-1个结点，由此数组下标从0开始，依次排布，通过前人所总结，可以通过左孩子右孩子的结点计算出父亲的下标，也可以通过父亲的下标计算出左孩子和右孩子的下标，计算公式如下图。
向下调整算法，以小堆为例子，即在根的左右子树的小堆的情况下，从根结点开始，依次选出左右孩子中小的那一个，并和根比较，若两者中小的那个小于根，那便把根和小的那一个孩子交换，根换成新的根，孩子换成新的孩子，如果孩子中小的那一个比根大，那说明排好了，不需要向下调整了。
向下调整算法的弊端也十分明显，那便是限制条件，即必须根的左右子树需要为小堆，并不是所有时候左右子树都是小堆，那该怎么办呢？
我们站在巨人的肩膀上看世界，通过研究，我们不难发现，从最后一个非叶子结点依次向根依次进行向下调整，那么最后进行到根节点时，左右子树就已经都向下调整完了，那就符合左右子树都是小堆了，再经过研究，叶子结点好像并不需要调整，由此我们只需要找到最后一个非叶子结点开始依次向根出发即可，如何找呢？不难想到下标为n-1的结点是最后一个结点，即最后一个非叶子结点的孩子，那我们便可以通过叶子去找到父亲即最后一个非叶子结点。
至此我们的建堆操作便全部完成了，接下来正式进入排序环节：
第一个要思考的问题就是如果我们要排升序，是建大堆还是建小堆，许多人包括我在内第一个想法都是小堆，因为小堆的根是最小的元素，我们可以这样依次排下去，但是并不是这样，倘若我们建了小堆，那要取出的元素就是最小的元素即总根，总根拿走了，整个树的结构全部都变了，需要再次进行向下调整，那复杂度和直接简单的选择排序有什么区别呢？所以我们排升序时需要建大堆，把大堆的根即为最大的元素，和最后一个元素交换，再把最后一个元素删去，删去最后一个元素并不会影响整棵树的构造，因此无需完全再次使用一次完整的向下调整算法，而只需要简单的调整（即删去一个树的最后一个结点重新简单地向下微调整)。
堆排序由于建堆只有大于才会交换，在从最后一个非叶子结点开始向下调整时，就会出现相对位置的变化，因此相同的值之间的相对位置可能发生变化，如建完堆后总根为9，总根的左子树也为9，第一次就会把总根的9放到最后相对位置就换了，因此堆排序不稳定。
def adjustdown(li,n,root): # 建立小堆
parent = root
child = 2*parent + 1
while child < n:
if child+1<n and li[child + 1]>li[child]: # 注意越界情况
child+=1
if li[child]>li[parent]:
li[child],li[parent] = li[parent],li[child]
parent = child
child = 2 * parent + 1
else:
break
def heapsort(li:list):
length = len(li)
i = (length - 2) // 2
while i >= 0: # 从第一个非叶子结点开始向根做调整
adjustdown(li,length,i)
i-=1
end = len(li) - 1
while end >= 0:
li[0],li[end] = li[end],li[0]
adjustdown(li,end,0)
end-=1
deque模块的使用实现堆排序：（这个办法不太好，图上已经附上解释）
import heapq
def heapq_sort(li:list):
heapq.heapify(li) # 默认建立小堆
new_list = []
for i in range(len(li)):
num = heapq.heappop(li) # 将最小的元素弹出，并重新建立小堆
new_list.append(num) # 加入新列表
li = new_list.copy() # 拷贝至原列表6.快速排序 O（logn*n）
如图所示，快排的原理就是选定一个数，将比这个数大的数放在其后方，小的放在前方，然后进行递归，直到无法解决的子问题。
快速排序的思想，即随便在数组中找到一个数，并且用key将其储存起来，把比key大的元素放在key的后面，把比key小的元素放在key的前面，最后把key放到最后的位置，而此时key的位置已经是正确的了，所以我们不需要把key这个元素纳入考虑的范围了，一轮过后将数组分为三个部分，第一部分是key元素单独自己，第二部分是key元素的左边，即比key小的元素范围，其范围是[left,key的位置-1]，第三部分是key元素的右边，其范围是[key的位置+1，right]，再利用分治的思想，将这两个部分继续快排，直到只有一个元素或者0个元素，这两种情况都视为有序。
完成一轮快排后，不难想到，这里我们需要借助分治的思想来解决问题，即排完一次后，将key前面的一组数据视为新的区间，后面一组数据同样也看作新区间，分别进行快排，所以这个时候我们传入的参数就需要修改了，修改成left和right也就是左区间和右区间，思想在上文已经提到过了，实现的代码如下：分治时间复杂度（LogN）
def midindex(li:list,left,right): # 三数取中的优化
mid = (left+right)//2
if li[mid] > li[left]:
if li[right] < li[left]:
return left
elif li[right] > li[mid]:
return mid
else:
return right
else: # li[mid] < li[left]
if li[right] < li[mid]:
return mid
elif li[right] > li[left]:
return left
else:
return right
def quick_sort(li:list,left:int,right:int):
if left >= right:
return
index = midindex(li,left,right)
li[left],li[index] = li[index],li[left]
begin = left
end = right
key = li[begin]
pivot = begin
while begin < end:
while li[end] > key and begin < end: # 找小
end-=1
li[end],li[pivot] = li[pivot],li[end]
pivot = end
while li[begin] < key and begin < end: # 找大
begin+=1
li[begin],li[pivot] = li[pivot],li[begin]
pivot = begin
li[pivot] = key
if pivot-1-left < 10: # 小区间优化
quick_sort(li,left,pivot-1)
else:
li[left:pivot] = insert_sort(li[left:pivot])
if right - pivot - 1 <10:
quick_sort(li,pivot+1,right)
else:
li[pivot+1:right+1] = insert_sort(li[pivot+1:right+1])Quicksort 的优化：前文中我们提到快排在排序已经有序的数组时，时间复杂度会变成N^2,这也正是我们需要优化快排的地方，这里我们引入一种方法叫做三数取中法，顾名思义就是找出三个数，我们不要最大的也不要最小的，这样就可以保证快排在挪动数据时的时间复杂度比较小，这三个数我们分别从边界的最左端值和最右端值以及其中间的那个数。
为了保证我们的key仍然是取下标为begin的值，所以我们找到不是最大也不是最小的中间值的下标后，可以利用swap函数把index和begin位置互换，这样key取到的还是begin位置的数，但是这个数已经被换成中间值了，这便是三数取中的思想。
快排相同元素相对位置会变化，如第一个key就是出现两次的值，那么最后key会在相同的值的后面，导致位置变化，因此快排不稳定。
Quicksort的优化：小区间优化，在不断分组分治时，一旦分割到足够小就会直接有序，但是我们不妨设想一个区间内只有十个值，我们却还要不断地分为5个2个1个，这未免有些太过繁琐，浪费了分治带来的快捷，因此一旦区间内的值少于10个，我们采用另外一种排序方法来对小区间进行排序，我们选择了插入排序（作者也不知道为什么，库里面是这样的，如果读者晓得，也可以告诉我）。
7.归并排序 O（n*logn）
def merge_sort(li:list,left,right,temp:list):
if left >= right: # 递归结束条件
return
else:
mid = (left+right)//2
merge_sort(li,left,mid,temp)
merge_sort(li,mid+1,right,temp) # 分治
# 归并，采用双指针法
begin1,end1 = left,mid
begin2,end2 = mid+1,right
index = left # 通用化
while begin1<=end1 and begin2<=end2:
if li[begin1] < li[begin2]:
temp[index] = li[begin1]
begin1 += 1
index += 1
else:
temp[index] = li[begin2]
begin2 += 1
index += 1
while begin1 <= end1:
temp[index] = li[begin1]
index += 1
begin1 += 1
while begin2 <= end2:
temp[index] = li[begin2]
index += 1
begin2 += 1
for i in range(left,right+1):
li[i] = temp[i] # 赋值到原列表中归并思想十分重要，其思想源于双指针法，假设两数组分别有序，如下图
我们想要将两数组升序合并到一个数组中，即创建一个新的数组，分别用两个指针指向两个有序数组的开头元素，并对比，将小的那一个拿下来放入新数组，让指针加加，直到一个数组内元素全部放入，这时我们不讨论哪个数组内还有元素，我们全部纳入考虑，即第一个数组如果没到边界，就让第一个数组内的元素依次放入新数组，第二个同理。
利用这个思想，我们进行归并排序，不难发现这个算法的关键是本身两数组就已经有序才可以进行合并，那我们如何让两个数组都有序，即分治算法，将一堆元素分治到一个甚至0个元素，再进行合并，他自然就有序了，因此运用二分区间去分治（其中的临时数组与左右区间就不多说了，左右区间是递归一大重要条件）。
分治到一个之后，我们一个一个将其合并，将两个一个元素合并，再将两个两个元素合并，以此类推，最后全部合并，即下列的归并操作，注意代码内容都是区间制，而非特殊例子。
tips：合并的时候让左区间的值先下来归并，即可让归并排序稳定。
8.计数排序 O（n+range)(range = max - min)
def count_sort(li:list,max:int,min:int):
range_ = max - min
temp = [0 for _ in range(0,range_+1)]
for i in range(0,len(li)):
temp[li[i]-min] += 1
li.clear()
for index,val in enumerate(temp):
for i in range(0,val): # 根据对应列表值来确定个数
li.append(index+min) # 加上对应偏移量 总体思想：即映射区间，将元素划分为对应的映射下标，然后记录出现次数，再一一映射回原来的列表。
计数排序的弊端很明显，其对负数无法进行排序，只有大于等于0的非负整数才可以使用计数排序，首先我们依据待排序列表中的最大值和最小值来确定映射的范围，如对90到99的数字进行排序，如果我们基于最大值加1的范围来确定映射范围，那么就要创建一个100的列表，但是这样前90个空间就被浪费了，因此我们依据待排序列表中的最大值和最小值来确定映射的范围，而将最小值作为基准来映射，如95就减去最小值90，映射到5的位置上，同时输出元素时，还需要对下标加上偏移量。
由于映射的特性，出现多次的数字对其来说都一样，我们并不讨论计数排序的稳定性。
总结：以上就是排序的大致内容，排序思想中最重要的就是对时间复杂度的考虑，我们要做的是不断优化，得到最快的排序算法，没有一种排序算法是万能的，我们只能观察题目来判断利用哪一种思想，此外，作者在这里提供一个时间装饰器方便读者自己来测试速度，对排序有更好的理解。
import time
def cal_time(func):
def wrapper(*args,**kwargs):
t1 = time.time()
result = func(*args,**kwargs)
t2 = time.time()
print(f"{func.__name__} running time is {t2-t1} secs")
return result
return wrapper
