【一、项目背景详细介绍】

排序算法是计算机科学中基础且关键的算法，广泛应用于数据处理、搜索、图形渲染等诸多领域。堆排序（Heap Sort）是一种基于堆（Heap）数据结构的比较排序算法，时间复杂度稳定为O(n log n)，且为原地排序。堆排序利用大顶堆或小顶堆特性，反复将堆顶元素（最大或最小）与末尾交换，并调整堆结构，实现数组整体有序。

与快速排序相比，堆排序最坏情况仍为O(n log n)，且无需递归调用过深的栈。但堆排序不稳定，不保留相等元素原有相对顺序。由于其空间开销仅为O(1)，在对内存敏感场景中具有一定优势。

【二、项目需求详细介绍】

1. 功能需求

   • 在Java环境中实现Heap Sort算法，能对整型数组和泛型对象数组进行升序与降序排序。

   • 提供buildMaxHeap与heapify等核心方法的模块化实现，并在注释中说明原理。

2. 性能需求

   • 时间复杂度：建堆O(n)，调整堆O(log n)，整体O(n log n)；

   • 空间复杂度：O(1)，原地排序，不使用额外数组。

3. 代码质量需求

   • 结构清晰：入口方法、堆构建、堆调整、交换方法分别实现；

   • 注释完备：对堆索引计算、向下调整过程、泛型支持等关键步骤详细说明；

   • 包含main方法示例及JUnit测试框架示例。

【三、相关技术详细介绍】

1. 数组表示的完全二叉树

   • 利用下标i的父节点索引为(i-1)/2，左右子节点索引分别为2*i+1和2*i+2；

2. 堆的两大操作

   • buildMaxHeap：自底向上调用heapify，初始建堆时间O(n)；

   • heapify：向下调整节点，使子树满足堆性质，时间O(log n)。

3. 泛型与Comparable接口

   • 使用<T extends Comparable<T>>支持任意可比较对象；

   • 比较时调用compareTo并根据升降序切换方向。

4. 原地交换

   • 通过临时变量或三元交换将堆顶与末尾元素互换，保持原地特性。

【四、实现思路详细介绍】

1. 主流程

   • 调用heapSort(arr, ascending)；

   • buildHeap(arr, ascending)：构建大顶堆或小顶堆；

   • 依次将堆顶与末尾arr[heapSize-1]交换，再对arr[0..heapSize-2]执行heapify，更新heapSize--；

2. 堆构建

   • 从最后一个非叶子节点i = (n/2)-1向前遍历至0，调用heapify(arr, i, heapSize, ascending)；

3. 向下调整（heapify）

   • 比较节点i与其左右子节点，选出较大（或较小）者largest，若largest != i，交换并继续对largest位置递归调整；

4. 升降序切换

   • 升序使用大顶堆，堆顶最大；降序使用小顶堆，堆顶最小；

   • 在比较逻辑中根据ascending切换>或<。

【五、完整实现代码】

// 文件：HeapSort.java
// 描述：基于数组原地堆排序实现，支持泛型与升降序

import java.util.Arrays;

public class HeapSort {

    /**
     * 对整型数组进行堆排序
     */
    public static void heapSort(int[] arr, boolean ascending) {
        if (arr == null || arr.length < 2) return;
        int n = arr.length;
        buildHeap(arr, n, ascending);
        for (int size = n; size > 1; size--) {
            swap(arr, 0, size - 1);
            heapify(arr, 0, size - 1, ascending);
        }
    }

    private static void buildHeap(int[] arr, int size, boolean asc) {
        for (int i = (size / 2) - 1; i >= 0; i--) {
            heapify(arr, i, size, asc);
        }
    }

    private static void heapify(int[] arr, int i, int size, boolean asc) {
        int extreme = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < size && (asc ? arr[left] > arr[extreme] : arr[left] < arr[extreme])) {
            extreme = left;
        }
        if (right < size && (asc ? arr[right] > arr[extreme] : arr[right] < arr[extreme])) {
            extreme = right;
        }
        if (extreme != i) {
            swap(arr, i, extreme);
            heapify(arr, extreme, size, asc);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 泛型版本堆排序
     */
    public static <T extends Comparable<T>> void heapSort(T[] arr, boolean ascending) {
        if (arr == null || arr.length < 2) return;
        int n = arr.length;
        buildHeap(arr, n, ascending);
        for (int size = n; size > 1; size--) {
            swap(arr, 0, size - 1);
            heapify(arr, 0, size - 1, ascending);
        }
    }

    private static <T extends Comparable<T>> void buildHeap(T[] arr, int size, boolean asc) {
        for (int i = (size / 2) - 1; i >= 0; i--) {
            heapify(arr, i, size, asc);
        }
    }

    private static <T extendsComparable<T>> void heapify(T[] arr, int i, int size, boolean asc) {
        int extreme = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < size && (asc ? arr[left].compareTo(arr[extreme]) > 0 : arr[left].compareTo(arr[extreme]) < 0)) {
            extreme = left;
        }
        if (right < size && (asc ? arr[right].compareTo(arr[extreme]) > 0 : arr[right].compareTo(arr[extreme]) < 0)) {
            extreme = right;
        }
        if (extreme != i) {
            swap(arr, i, extreme);
            heapify(arr, extreme, size, asc);
        }
    }

    private static <T> void swap(T[] arr, int i, int j) {
        T tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 测试示例
    public static void main(String[] args) {
        int[] data = {5, 3, 8, 4, 2, 7, 1};
        System.out.println("原始：" + Arrays.toString(data));
        heapSort(data, true);
        System.out.println("升序：" + Arrays.toString(data));
        heapSort(data, false);
        System.out.println("降序：" + Arrays.toString(data));

        String[] strs = {"d","b","a","c"};
        System.out.println("原始字符串：" + Arrays.toString(strs));
        heapSort(strs, true);
        System.out.println("排序后：" + Arrays.toString(strs));
    }
}

【六、代码详细解读】

• buildHeap：从最后一个非叶子节点开始，自底向上构建堆；

• heapify：向下调整节点，维护堆性质；

• heapSort 主流程：先建堆，再交换堆顶与末尾并缩小堆规模，直到完成排序；

• 泛型版本通过compareTo实现对象比较，逻辑与整型版一致。

【七、项目详细总结】

堆排序通过堆这种特殊的完全二叉树结构，实现了原地且稳定时间复杂度为O(n log n)的排序方法。建堆与调整堆操作分别为O(n)与O(log n)，总计O(n log n)。虽然堆排序不稳定，但其空间开销小、最坏情况性能可控，适用于内存敏感与实时性要求较高的场景。

【八、项目常见问题及解答】

1. 问：堆排序是稳定的吗？
   答：堆排序不是稳定排序，因为交换堆顶与末尾元素会打乱相等元素原有顺序。

2. 问：为什么建堆时间为O(n)而非O(n log n)？
   答：自底向上的heapify在树的底部操作次数多但路径短，综合计算为O(n)。

3. 问：如何优化堆排序的常数项？
   答：可使用三项交换或无临时变量交换减少赋值次数，或在调整过程中减少递归改为迭代。

【九、扩展方向与性能优化】

1. 二项堆与斐波那契堆：研究更高级堆结构在优先队列中的应用；

2. 外部堆排序：结合外部存储，将堆用于海量数据排序；

3. 并行堆排序：在多核环境下并行化建堆与划分；

4. 组合排序：将堆排序与插入排序等算法结合，提升小数据集性能；

5. 软堆：允许少量错误以获取更优时间或空间表现。