题5
题目
Q:就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系是 ( ).
A. 堆排序<快速排序<归并排序
B. 堆排序<归并排序<快速排序
C. 堆排序>归并排序>快速排序
D. 堆排序>快速排序>归并排序
分析
A:归并排序需要额外的空间，快排和堆排不需要额外的空间，所以堆排序<快速排序<归并排序
解
A
由于堆排序的空间复杂度为
Q:堆排序的空间复杂度？
A:1. 堆排序 - O(1)
- 原地操作: 堆排序的核心是维护一个堆结构，并在数组内部进行调整。它不需要创建额外的数组或存储大量数据。
- 空间恒定: 不论输入数组规模大小，堆排序额外使用的空间基本保持不变，所以它的空间复杂度是O(1), 也称为原地排序。
Q:快排的空间复杂度？
A:2. 快速排序 - O(log n) 到 O(n)
- 递归调用: 快速排序使用递归来排序子数组。 每次递归调用都需要在栈上存储一些信息，例如数组索引。
- 平均情况: 在平均情况下，递归深度为 O(log n)，所以空间复杂度为 O(log n)。
- 最坏情况: 当数组近乎有序或逆序时，递归深度最坏会达到 O(n)，导致空间复杂度为 O(n)。
Q:归并排序的空间复杂度？
A:3. 归并排序 - O(n)
- 合并步骤: 归并排序的核心是将两个有序子数组合并成一个更大的有序数组。这个合并操作需要额外的空间来存储合并结果。
- 线性空间: 对于规模为 n 的数组，合并步骤需要一个大小为 n 的辅助数组，所以空间复杂度为 O(n)。