使用Java编写堆排序算法

堆排序是一种比较高效的排序算法，它基于二叉堆的数据结构来实现排序。堆是一个完全二叉树，它具有以下两个特性：

1. 最大堆特性：对于堆中的任意节点i，其父节点的值大于或等于节点i的值。

2. 最小堆特性：对于堆中的任意节点i，其父节点的值小于或等于节点i的值。

堆排序的基本思路是：

1. 将待排序的数组构建为一个最大堆。

2. 将堆顶元素与堆中的最后一个元素交换，并将堆的大小减1。

3. 重复步骤2，直到堆为空。

4. 逆序输出交换出的元素，即为排序后的数组。

下面是使用Java编写的堆排序算法的实现：

public class HeapSort {
    public static void heapify(int[] array, int length, int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < length && array[left] > array[largest]) {
            largest = left;
        }

        if (right < length && array[right] > array[largest]) {
            largest = right;
        }

        if (largest != i) {
            int swap = array[i];
            array[i] = array[largest];
            array[largest] = swap;
            heapify(array, length, largest);
        }
    }

    public static void heapSort(int[] array) {
        if (array.length == 0) return;

        int length = array.length;

        // 构建最大堆
        for (int i = length / 2 - 1; i >= 0; i--)
        heapify(array, length, i);

        // 交换堆顶元素与最后一个元素，并重新构建最大堆
        for (int i = length - 1; i >= 0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;

            heapify(array, i, 0);
        }
    }

    public static void printArray(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6, 7};
        System.out.println("原始数组：");
        printArray(array);

        heapSort(array);

        System.out.println("排序后的数组：");
        printArray(array);
    }
}

上述代码首先定义了一个

方法，用于构建最大堆以及调整堆的结构。然后定义了
方法，其中首先构建最大堆，然后通过交换堆顶元素与末尾元素，调整堆的结构。最后通过
方法输出排好序的数组。


在
方法中，可以生成一个随机数组，然后调用
方法对数组进行排序，并通过
方法将结果输出。