快速排序

快速排序是一种基于**分治思想（Divide and Conquer）**的算法>排序算法。其核心思想是：

1. 选择一个基准元素（pivot），通常是数组中的某个元素（如最左/最右元素、中间元素或随机选择）。
2. 通过**分区（partition）**操作，将小于基准的元素放到基准左侧，大于基准的元素放到基准右侧。
3. 对左右两个子数组递归地进行快速排序，直到子数组长度为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，右侧大于 pivoti += 1  # 左指针右移j -= 1  # 右指针左移# 递归处理左子数组if l < j: qsort(arr, l, j)# 递归处理右子数组if i < r: qsort(arr, i, r)

堆排序

堆排序是一种基于比较的算法>排序算法，利用了堆这种数据结构（通常是二叉堆）来完成排序。堆是一棵完全二叉树，具有以下性质：

• 最大堆（Max-Heap）：父节点的值大于或等于子节点的值。
• 最小堆（Min-Heap）：父节点的值小于或等于子节点的值。

堆排序的步骤：

1. 构建堆：首先将待排序的数组转换为一个堆。通常构建的是最大堆（对于升序排序），即堆顶元素是数组中最大的元素。
2. 交换根节点与最后一个元素：将堆顶元素（最大元素）与堆的最后一个元素交换。
3. 重新调整堆：将新的根节点调整为满足堆的性质，恢复最大堆。
4. 重复步骤 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)  # 调整剩余部分为最大堆