面试题：C++ 堆排序与其他排序算法的性能比较及应用场景

时间复杂度

堆排序：平均时间复杂度为 $O(nlogn)$，最坏时间复杂度也为 $O(nlogn)$。它每次调整堆的操作时间复杂度为 $O(logn)$，总共需要 $n$ 次调整，所以总体时间复杂度为 $O(nlogn)$。
快速排序：平均时间复杂度为 $O(nlogn)$。但最坏情况下（如每次选取的基准元素都是当前序列中的最大或最小元素），时间复杂度为 $O(n^2)$。因为划分操作可能会使序列极度不均匀，导致递归深度达到 $n$。
归并排序：平均时间复杂度和最坏时间复杂度均为 $O(nlogn)$。归并排序主要操作是归并操作，每次归并操作的时间复杂度与序列长度成正比，总共需要 $logn$ 层归并，所以时间复杂度为 $O(nlogn)$。

空间复杂度

堆排序：空间复杂度为 $O(1)$。堆排序是在原数组上进行操作，只需一些常数级别的额外空间用于交换元素等操作。
快速排序：平均空间复杂度为 $O(logn)$。这是因为快速排序递归调用需要栈空间，平均递归深度为 $logn$。但最坏情况下，由于递归深度达到 $n$，空间复杂度为 $O(n)$。
归并排序：空间复杂度为 $O(n)$。归并排序在归并过程中需要一个与原数组大小相同的辅助数组来暂存数据。

稳定性

堆排序：不稳定。例如序列 [2, 1, 2']，在堆排序过程中，相同元素 2 和 2' 的相对顺序可能会改变。
快速排序：不稳定。在划分过程中，相同元素的相对顺序可能会发生变化。例如序列 [2, 1, 2']，以 2 为基准划分后，2 和 2' 的相对顺序可能改变。
归并排序：稳定。在归并操作中，当遇到相等元素时，先将前面的元素放入辅助数组，保证了相等元素的相对顺序不变。

优先选择堆排序的场景及实现方案

业务场景：当需要对大量数据进行排序，并且内存空间有限，不希望使用额外过多空间，同时对稳定性没有要求时，优先选择堆排序。例如在操作系统的进程调度算法中，需要对大量进程按照优先级进行排序，进程调度算法通常对空间要求严格，且不关心相同优先级进程的顺序，此时堆排序较为合适。

C++ 实现简要方案：

#include <iostream>
#include <vector>

// 调整堆，使以 i 为根的子树成为大顶堆
void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i; // 初始化最大元素为根节点
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点

    // 如果左子节点大于根节点
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 如果右子节点大于最大元素
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果最大元素不是根节点
    if (largest != i) {
        std::swap(arr[i], arr[largest]);

        // 递归调整受影响的子树
        heapify(arr, n, largest);
    }
}

// 堆排序函数
void heapSort(std::vector<int>& arr) {
    int n = arr.size();

    // 建立大顶堆
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 一个一个地从堆顶取出元素
    for (int i = n - 1; i > 0; i--) {
        // 将当前堆顶元素移到数组末尾
        std::swap(arr[0], arr[i]);

        // 调用堆调整函数，调整剩余元素
        heapify(arr, i, 0);
    }
}

使用示例：

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    heapSort(arr);

    std::cout << "排序后的数组: ";
    for (int num : arr)
        std::cout << num << " ";

    return 0;
}

星途面试题库

面试题：C++ 堆排序与其他排序算法的性能比较及应用场景

知识考点

面试题答案

时间复杂度

空间复杂度

稳定性

优先选择堆排序的场景及实现方案