堆排序的时间复杂度和空间复杂度

### 堆排序的时间复杂度和空间复杂度分析 堆排序是一种基于比较的排序算法，其时间复杂度和空间复杂度可以通过详细分析得出。 #### 时间复杂度分析 堆排序的时间复杂度主要由两个部分组成：建堆过程和调整堆的过程。 1. **建堆的时间复杂度** 建堆的过程是从最后一个非叶子节点开始，逐层向上调整堆。对于一个高度为 \(k\) 的完全二叉树，节点总数 \(n = 2^k - 1\)，因此高度 \(k = \log(n+1)\)。建堆的总执行次数可以表示为 \(S = 2^{k+1} - k - 2\)，将其化简后得到 \(S = 2n - \log(n+1)\)。由此可知，建堆的时间复杂度为 \(O(n)\)[^2]。 2. **调整堆的时间复杂度** 在堆排序过程中，每次将堆顶元素与最后一个元素交换后，需要重新调整堆以保持最大堆或最小堆的性质。调整堆的操作涉及从根节点向下调整，其时间复杂度为 \(O(\log n)\)，因为调整堆的高度为 \(\log n\)。整个调整堆的过程需要进行 \(n-1\) 次循环，每次循环的时间复杂度为 \(O(\log i)\)，因此总的时间复杂度为 \(O(n \log n)\)[^1]。 综合以上两部分，堆排序的整体时间复杂度为 \(O(n \log n)\)[^3]。 #### 空间复杂度分析 堆排序是一种原地排序算法，除了输入数组外，不需要额外的存储空间。在堆排序的过程中，仅使用了常数级别的额外变量（如用于交换的临时变量），因此其空间复杂度为 \(O(1)\)[^4]。 ```python def heapSort(arr): if arr is None or len(arr) < 2: return def heapify(arr, index, heap_size): largest = index left = 2 * index + 1 right = 2 * index + 2 if left < heap_size and arr[left] > arr[largest]: largest = left if right < heap_size and arr[right] > arr[largest]: largest = right if largest != index: arr[index], arr[largest] = arr[largest], arr[index] heapify(arr, largest, heap_size) def swap(arr, i, j): arr[i], arr[j] = arr[j], arr[i] # 建堆 O(N) for i in range(len(arr) // 2 - 1, -1, -1): heapify(arr, i, len(arr)) heap_size = len(arr) while heap_size > 0: swap(arr, 0, heap_size - 1) heap_size -= 1 heapify(arr, 0, heap_size) ``` #### 总结 堆排序的时间复杂度为 \(O(n \log n)\)，空间复杂度为 \(O(1)\)。