手写一个堆排序

好的，以下是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);
        }
    }

    // 以根节点为i的子树为最大堆
    void heapify(int[] arr, int n, int i) {
        int largest = i;
        int l = 2 * i + 1;  // 左子节点
        int r = 2 * i + 2;  // 右子节点

        // 如果左子节点比根节点大，则更新最大值
        if (l < n && arr[l] > arr[largest])
            largest = l;

        // 如果右子节点比最大值大，则更新最大值
        if (r < n && arr[r] > arr[largest])
            largest = r;

        // 如果最大值不是根节点，则交换根节点和最大值，并继续向下调整
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }
}

在堆排序中，我们首先构建一个最大堆，然后依次将堆顶元素移到数组末尾，并重新构建最大堆。`heapify()`方法用于将以根节点为i的子树调整为最大堆，其中n表示当前堆的大小。在`heapify()`方法中，我们首先找到根节点、左子节点和右子节点中的最大值，如果最大值不是根节点，则交换根节点和最大值，并继续向下调整。在堆排序中，时间复杂度为O(nlogn)，空间复杂度为O(1)。