面试官问：Java堆排序算法的原理和实现，你能详细解答吗？

堆排序是一种基于比较的排序算法，它利用了堆这种数据结构。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

原理

堆排序的基本思想是：

1. 构建堆：将无序的输入数据构建成一个最大堆（大顶堆或小顶堆）。
2. 调整堆：将堆顶元素（即最大元素）与堆的最后一个元素交换，然后将剩余的元素（除了最后一个）重新调整成最大堆。
3. 重复步骤：重复步骤2，直到堆中只剩下一个元素，此时数组已经是有序的。

在Java中，我们通常使用大顶堆进行堆排序。

最大堆的性质

• 对于最大堆，每个父节点的值都大于或等于其子节点的值。
• 堆通常以数组的形式实现，其中父节点的索引为i，其左子节点的索引为2i + 1，右子节点的索引为2i + 2。

实现步骤

1. 构建最大堆：从最后一个非叶子节点开始，向上调整，直到根节点。
2. 排序：交换堆顶元素与最后一个元素，然后调整剩余元素形成的堆。

Java代码实现

以下是使用Java实现堆排序的示例代码：

public class HeapSort {

    public void sort(int arr[]) {
        int n = arr.length;

        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 排序
        for (int i = n - 1; i > 0; i--) {
            // 交换堆顶元素与最后一个元素
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 调整剩余元素形成的堆
            heapify(arr, i, 0);
        }
    }

    // 调用heapify函数来调整堆
    void heapify(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) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

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

    // 打印数组
    public void printArray(int arr[]) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    // 测试堆排序
    public static void main(String args[]) {
        HeapSort hs = new HeapSort();
        int arr[] = {12, 11, 13, 5, 6, 7};
        int n = arr.length;

        System.out.println("Original array:");
        hs.printArray(arr);

        hs.sort(arr);

        System.out.println("Sorted array:");
        hs.printArray(arr);
    }
}

总结

堆排序的时间复杂度为O(n log n)，它是一个不稳定的排序算法。尽管它的最坏情况时间复杂度与其他排序算法相同，但堆排序在实践中的应用并不常见，因为它的常数因子相对较高，且它不是原地排序算法（需要额外的空间来构建堆）。不过，堆排序在数据量大且对稳定性没有要求的情况下，仍然是一个值得考虑的选择。