面试准备-排序部分：快速排序、堆排序
快速排序
快速排序是一种基于**分治思想（Divide and Conquer）**的排序算法。其核心思想是：
- 选择一个基准元素（pivot），通常是数组中的某个元素（如最左/最右元素、中间元素或随机选择）。
- 通过**分区（partition）**操作，将小于基准的元素放到基准左侧，大于基准的元素放到基准右侧。
- 对左右两个子数组递归地进行快速排序，直到子数组长度为1或0（即已排序）。
快排的时间复杂度取决于基准选择的好坏：
最优情况（O(n log n)）：每次都能将数组均匀划分，递归深度为log n，每层的分区操作是 O(n)，所以总复杂度是 O(n log n)。最坏情况（O(n²)）：如果每次选择的基准导致极端不均匀划分（如已排序数组选择最左/最右元素），递归深度达到 O(n)，每层 O(n)，总复杂度 O(n²)。
平均情况（O(n log n)）：随机选取基准时，通常能保证 O(n log n) 的复杂度。
快排的空间复杂度：
**原地排序版本（Hoare 版）**的快速排序只需要 O(1) 的额外空间。递归调用栈的空间复杂度为 O(log n)（理想情况）到 O(n)（最坏情况）。
改进措施：采用尾递归优化，可以减少栈的使用深度。
快速排序是不稳定的，因为交换操作可能改变相同元素的相对位置。
代码：
def qsort(arr: list, l: int, r: int) -> None:
if l >= r: # 递归终止条件，当子数组长度 ≤ 1 时返回
return
# 选择中间元素作为 pivot（基准值）
i, j, p = l, r, arr[(l + r) >> 1]
# 分区操作
while i <= j:
# 从左向右找到第一个不小于 pivot 的元素
while arr[i] < p:
i += 1
# 从右向左找到第一个不大于 pivot 的元素
while arr[j] > p:
j -= 1
# 当 i <= j 时，交换两侧的元素
if i <= j:
arr[i], arr[j] = arr[j], arr[i] # 交换元素，使得左侧小于 pivot，右侧大于 pivot
i += 1 # 左指针右移
j -= 1 # 右指针左移
# 递归处理左子数组
if l < j: qsort(arr, l, j)
# 递归处理右子数组
if i < r: qsort(arr, i, r)
堆排序
堆排序是一种基于比较的排序算法，利用了堆这种数据结构（通常是二叉堆）来完成排序。堆是一棵完全二叉树，具有以下性质：
- 最大堆（Max-Heap）：父节点的值大于或等于子节点的值。
- 最小堆（Min-Heap）：父节点的值小于或等于子节点的值。
堆排序的步骤：
- 构建堆：首先将待排序的数组转换为一个堆。通常构建的是最大堆（对于升序排序），即堆顶元素是数组中最大的元素。
- 交换根节点与最后一个元素：将堆顶元素（最大元素）与堆的最后一个元素交换。
- 重新调整堆：将新的根节点调整为满足堆的性质，恢复最大堆。
- 重复步骤 2 和 3，直到堆的大小减少到 1。
时间复杂度：
- 构建堆：
O(n) - 调整堆：每次调整堆的时间复杂度是
O(logn)，总共需要进行 n 次调整，因此整体时间复杂度为O(nlogn)。
堆排序是 不稳定的排序，可能会改变相同元素的相对顺序。
def heapify(arr:list, n:int, i:int):
"""
将一个子树调整为最大堆，n是堆的大小，i是当前根节点的索引
"""
largest = i # 初始化最大值为根节点
left = 2 * i + 1 # 左子节点索引
right = 2 * i + 2 # 右子节点索引
# 如果左子节点大于根节点
if left < n and arr[left] > arr[largest]:
largest = left
# 如果右子节点大于根节点
if right < n and arr[right] > arr[largest]:
largest = right
# 如果根节点不是最大，交换并递归堆化
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # 交换
heapify(arr, n, largest) # 递归调整子树
def heap_sort(arr):
"""
堆排序的主函数
"""
n = len(arr)
# 构建最大堆
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 一个个从堆顶取出元素，并重新调整堆
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # 交换堆顶元素和当前末尾元素
heapify(arr, i, 0) # 调整剩余部分为最大堆