目录
快速排序（quick sort）
1.什么是快速排序
递归是快速排序的精髓，基本原理是采用分治法策略，把一个序列分为较小和较大的2个子序列，然后递归的排序子序列。
2.快速排序思路
1.首先挑选一个元素作为基准值（pivot）
2.分割重新排序数列，所以比基准值小的排在基准值一边，比基准值大的排在另外一边，完成基于基准值的排序
3.递归排序子序列：递归的将每次的基准值的左右两边排序，递归最底部的条件是判断数列元素大于1（left < right）
4.核心是partition函数，partition函数要做的是选择一个基准值（默认选择【left】），两个while循环实现基于基准值的排序
举例说明快速排序的思路
3.快速排序代码
def quick_sort(lst,left,right): # 需要传入一个列表lst，以及最左边后最后边的位置
if left < right: # 如果左边小于右边，则说明列表内至少有两个元素
mid = partition(lst,left,right) # 通过partition获得基准值mid
quick_sort(lst,left,mid-1) # 递归左边的元素
quick_sort(lst,mid+1,right) # 递归右边的元素那么快速排序的关键就在于如何设置基准值，即框架内的partition函数？
举例说明：
有如下列表
第一步：我们先存取“5”的位置，此时“5”的位置空出来，随后从左边和右边开始与“5”比较；
第二步：从最右边的位置的元素与“5”比较，如果比“5”大那么不动，发现比“5”小的（“2”）则放到刚刚空出来的“5”的位置；
第三步：移动了“2”之后原来“2”的位置就空出来，则从当前“2”的位置（左边）开始查找，将比“5”大的数（7）移动到原先“2”的位置；
第四步：重复第二到三步，直到左右的位置重合，即为“5”最终存放的位置
以上便是partition函数的思路（可能有点难理解）
实现快速排序算法代码
def partition(lst,left,right): # partition(分割)函数
tmp = lst[left] # 存放基准点，以最左边的值为例
while left < right: # 当左边的位置（下标）小于右边的时候，说明还有至少两个元素，则进行排序
while lst[right] >= tmp and left < right: # 从右边找比tmp小的元素
right -= 1 # 比tmp大，则往左移动一位
lst[left] = lst[right] # 如果出现lst[right] < tmp，则将右边的值lst[right]写到左边的空位lst[left]
# print(f"从右边找比tmp小的数后的列表:{lst}")
while lst[left] <= tmp and left < right: # 从左边找比tmp大的元素lst[left]，放到右边的空位上lst[right]
left += 1
lst[right] = lst[left]
# print(f"从左边找比tmp大的数后的列表:{lst}")
lst[left] = tmp # 最后把tmp归位
return left # 返回mid的值
# lst1 = [5,7,4,2,6,8,3,1,9]
# print(f"分割前的列表{lst1}")
# partition(lst1,0,len(lst1)-1)
# print(f"最终tmp归为后的列表:{lst1}")
# 输出结果
# 分割前的列表[5, 7, 4, 2, 6, 8, 3, 1, 9]
# 从右边找比tmp小的数后的列表:[1, 7, 4, 2, 6, 8, 3, 1, 9]
# 从左边找比tmp大的数后的列表:[1, 7, 4, 2, 6, 8, 3, 7, 9]
# 从右边找比tmp小的数后的列表:[1, 3, 4, 2, 6, 8, 3, 7, 9]
# 从左边找比tmp大的数后的列表:[1, 3, 4, 2, 6, 8, 6, 7, 9]
# 从右边找比tmp小的数后的列表:[1, 3, 4, 2, 6, 8, 6, 7, 9]
# 从左边找比tmp大的数后的列表:[1, 3, 4, 2, 6, 8, 6, 7, 9]
# 最终tmp归为后的列表:[1, 3, 4, 2, 5, 8, 6, 7, 9]
# 随后完成快速排序主体部分的代码
def quick_sort(lst, left, right): # 需要传入一个列表lst，以及最左边后最后边的位置
if left < right: # 如果左边小于右边，则说明列表内至少有两个元素
mid = partition(lst, left, right) # 通过partition获得基准值mid
quick_sort(lst, left, mid - 1) # 递归左边的元素
quick_sort(lst, mid + 1, right) # 递归右边的元素
lst2 = [5,7,4,2,6,8,3,1,9]
print(f"初始列表:{lst2}")
quick_sort(lst2,0,len(lst2)-1)
print(f"快速排序后的{lst2}")
# 输出结果
# 初始列表:[5, 7, 4, 2, 6, 8, 3, 1, 9]
# 快速排序后的[1, 2, 3, 4, 5, 6, 7, 8, 9]4快速排序复杂度
O(nlogn) （一层的复杂度是logn，总共n层）
5.快速排序函数与冒泡排序的效率比较
from runtime import *
import random,copy
@runtime
def bubble_sort(lst):
for i in range(len(lst) - 1): # 表示第i趟
exchange = False # 每一趟做标记
for j in range(len(lst)-i-1): # 表示箭头
if lst[j] > lst[j+1]: # 此时是升序排序，>改为<则改为了降序
lst[j],lst[j+1] = lst[j+1],lst[j]
exchange = True # 进行了交换，exchange标记为Ture
# print(f"第{i+1}趟后的列表为：{lst}") # 查看排序过程
if not exchange: # 如果没有进行交换，直接返回，优化的步骤
return
@runtime
def time_quick_sort(lst):
quick_sort(lst, 0, len(lst) - 1)
lst3 = list(range(10000))
random.shuffle(lst3)
lst_quick = copy.deepcopy(lst3)
lst_bubble = copy.deepcopy(lst3)
time_quick_sort(lst_quick)
bubble_sort(lst_bubble)
# 输出结果
# time_quick_sort执行用时0.0309906005859375s
# bubble_sort执行用时11.869966506958008s
6.快速排序的缺点
快速排序出现最糟糕情况时，例如列表从的元素是从10000到1，则突破了计算的最大深度，且复杂度达到了O(n2)，空间复杂度也达到了O(n)。
此时可以通过调整运算的最大深度来进行运算（import sys --> sys.setrecursionlimit（100000）），但仍然运算的时间会变长，那么如何修改呢？
解决办法：
使用shuffle函数打乱序列排序
此时可以通过修改基准值位置随机取来调整，这样虽然不可以完全避免最坏情况，但是最坏情况的概率会降低。
十大排序之四大排序总结
稳定性说明：
3 2 1 2 4
稳定的排序可以保证左右两边的2的位置不变；
当我们换成字典来看时：
{"name":'a',"age":18}
{"name":'b',"age":19}
{"name":'a',"age":20}
如果按字母排序，稳定的排序，两个‘a’的位置不会改变
总的来说，挨个移动比较的排序算法为稳定的排序。
代码的复杂度：代表代码难不难写，应个人能力和主观感受而定。