注：本文是在学习了acwing的算法基础课后撰写，主要用于记录python版本算法的模板。

1.快速排序

思想：用列表中的一个数(pivot)来分割列表，左侧的数都小于pivot，右侧的数都大于pivot。

步骤：
1.确定pivot。左、右、中点、随机都可以，选择不同代码上可能有细微区别。这里选择中点。
2.调整pivot左侧和右侧的数，使左侧的数都小于pivot，右侧的数都大于pivot。利用双指针。
3.递归处理左、右两段。

模板：

def quick_sort(nums, start, end):
    if start >= end:
        return
    left = start
    right = end
    
    # 1.确定pivot。这里选择中点。
    mid = (left + right) // 2
    pivot = nums[mid]
    
    # 2.调整pivot左侧和右侧的数，使左侧的数都小于pivot，右侧的数都大于pivot。利用双指针。
    while left <= right:
        while left <= right and nums[left] < pivot:
            left += 1
        while left <= right and nums[right] > pivot:
            right -= 1
        if left <= right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1       # 这边一定要left+=1,right-=1.否则如果nums[left] == nums[right] == pivot的话就跳不出循环了
            right -= 1
            
    # 3.递归处理左、右两段。
    quick_sort(nums, start, right)
    quick_sort(nums, left, end)

2.归并排序

思想：采用分治的思想，通过列表中的中点将列表划分为左右两部分，将左右两个列表分别排序后合并成一个列表。

步骤：
1.确定分界点（中点）。mid = (l+r) // 2
2.递归排序left和right
3.归并（合二为一），此时left和right都已有序，利用双指针逐个比较即可。

模板：

def merge_sort(nums):
    if len(nums) <= 1:
        return
    
    # 1.确定分界点（中点）
    mid = len(nums) // 2
    
    # 2.递归排序left和right
    L = nums[:mid]
    R = nums[mid:]
    merge_sort(L)
    merge_sort(R)
    
    # 3.归并（合二为一）
    i, j, k = 0, 0, 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            nums[k] = L[i]
            i += 1
        else:
            nums[k] = R[j]
            j += 1
        k += 1
        
    while i < len(L):
        nums[k] = L[i]
        k += 1
        i += 1
    while j < len(R):
        nums[k] = R[j]
        k += 1
        j += 1

时间复杂度图

时间复杂度.png

3.二分

思想：如果可以找到这样一个性质，将整个区间一分为二，一半满足、一半不满足，就可以寻找这个性质的边界点。
二分和单调性不等价，单调可以二分，二分不一定要求单调。

步骤：
1.确定pivot。左、右、中点、随机都可以，选择不同代码上可能有细微区别。这里选择中点。
2.调整pivot左侧和右侧的数，使左侧的数都小于pivot，右侧的数都大于pivot。利用双指针。
3.递归处理左、右两段。

整数二分模板：
整数二分涉及边界问题，故有两种模板。

整数二分.png

def binary_search_left(nums, x):
    l = 0
    r = len(nums) - 1
    while l < r:
        mid = (l + r) // 2
        if check(mid):     # check()函数用于检查是否满足左侧性质
            r = mid
        else:
            l = mid + 1
    else:
        return l
    
    
def binary_search_right(nums, x):
    l = 0
    r = len(nums) - 1
    while l < r:
        mid = (l + r + 1) // 2
        if check(mid):     # check()函数用于检查是否满足右侧性质
            l = mid
        else:
            r = mid - 1
    else:
        return l

实数二分模板：
实数二分由于不存在向上取整还是向下取整的问题，故无需讨论边界。

def binary_search(l, r):
    while r - l > 1e-8:      # 不一定是1e-8，具体根据精度要求来，经验上来说是精度要求乘1e-2
        mid = (l + r) / 2
        if pow(mid, 3) >= n:
            r = mid
        else:
            l = mid
    return l