改进的堆排序算法及其复杂度分析

堆排序是一种高效的排序算法，由威洛姆斯在1964年提出。它基于堆这种数据结构，其中堆是一个完全二叉树，确保每个节点的值都大于或等于（对于最大堆）或小于或等于（对于最小堆）其子节点的值。堆排序的主要步骤包括构建初始堆、交换堆顶元素（最大或最小元素）与末尾元素并调整堆以及重复这个过程直到排序完成。 原始的堆排序算法的时间复杂度为O(n log n)，空间复杂度为O(1)，因为它是一个原地排序算法，不需要额外的存储空间。在构建堆的过程中，每个节点最多需要进行log_2(n)次比较，而调整建新堆时调用Heapadjust过程n-1次，所以总比较次数为4n - 2。由于n个结点的完全二叉树深度为[log_2(n)] + 1，最坏情况下堆排序的时间复杂度为O(n log n)。 然而，当输入序列接近有序时，原始堆排序的效率会降低，因为尾部元素可能需要多次下筛到堆底，增加了比较次数。为了改进这种情况，提出了新的策略：从根节点开始，每次仅通过一次键比较使最大子节点上升，之后根据比较次数限制决定尾部元素的上升或下筛。这种改进减少了重新建堆过程中的键比较次数，特别是当序列基本有序时，优化了效率。 改进后的算法分为三个主要部分： 1. 建立初始堆：通过shift函数将数组元素调整为堆结构。 2. 重新建堆：在元素交换后，使用rebuild函数根据堆深度和比较次数限制来更高效地调整堆。 3. 主堆排序循环：反复执行堆调整和元素交换，直到所有元素排序完成。 在堆深度h ≤ [log_2 n]时，由于元素基本有序，重新建堆的过程可以更快地将尾部元素放到正确位置，减少了比较次数。 改进的堆排序算法通过优化元素的交换和堆调整策略，降低了在最佳和近乎最佳情况下的比较次数，提高了效率，但保持了O(n log n)的时间复杂度下限，这是任何比较排序算法的理论下限。这种改进尤其在处理基本有序的序列时表现出更好的性能。