堆排序稳定吗？

堆排序是一种基于完全二叉树的排序算法。它的时间复杂度为O(nlogn)，空间复杂度为O(1)，因此被广泛应用于工程实践中。但是，堆排序是否稳定呢？

什么是稳定性？

在排序算法中，稳定性是指排序后相同元素的相对位置是否发生变化。比如，对于输入序列[2, 5, 2, 4, 3]，如果排序算法是稳定的，那么排序后的结果应该是[2, 2, 3, 4, 5]，即相同元素的相对位置没有变化。如果排序算法不稳定，那么排序后的结果可能是[2, 2, 4, 3, 5]，即相同元素的相对位置发生了变化。

堆排序的稳定性

堆排序不是稳定的排序算法。其原因在于堆排序是通过不断交换堆顶元素和最后一个叶子节点的方式来进行排序的。在这个过程中，相同元素的相对位置可能会发生变化。

// 堆排序代码示例
void heap_sort(int arr[], int n) {
    // 建立初始大根堆
    for (int i = (n - 1) / 2; i >= 0; i--) {
        adjust_heap(arr, i, n);
    }
    // 不断交换堆顶元素和最后一个叶子节点
    for (int i = n - 1; i >= 1; i--) {
        swap(arr[0], arr[i]);
        adjust_heap(arr, 0, i);
    }
}

在上面的堆排序代码中，我们可以看到，adjust_heap函数用来调整堆顶元素的位置，保证其符合大根堆的性质。而在第二个for循环中，我们不断地将堆顶元素和最后一个叶子节点进行交换，并调整堆顶元素的位置，直到所有元素都被排序完毕。

在这个过程中，如果存在两个相同元素，且它们的位置不同，那么它们有可能会被交换到不同的位置，从而导致相同元素的相对位置发生变化。

堆排序的优缺点

虽然堆排序不是稳定的排序算法，但是它仍然有很多优点：

1. 时间复杂度为O(nlogn)，性能优秀。
2. 空间复杂度为O(1)，不需要额外的空间。
3. 适用于大规模数据的排序，因为不需要对整个序列进行排序，而是通过不断调整堆来实现排序。

当然，堆排序也有一些缺点：

1. 不是稳定的排序算法。
2. 不适用于小规模数据的排序，因为它的常数项比较大。
3. 实现较为复杂，容易出错。

常见问答

堆排序和快速排序有什么区别？

堆排序和快速排序都是基于比较的排序算法，但是它们的实现方式不同。快速排序是通过不断划分序列，并对子序列进行排序来实现排序的，而堆排序是通过不断调整堆来实现排序的。因此，堆排序的时间复杂度为O(nlogn)，而快速排序的时间复杂度为O(nlogn)或O(n)，具体取决于划分的方式。

堆排序适用于哪些场景？

堆排序适用于需要对大规模数据进行排序的场景，比如大数据量的数据库查询、搜索引擎排序等。它的优点在于时间复杂度低、不需要额外的空间，适用于处理海量数据。