如何使用java实现堆排序算法

如何使用Java实现堆排序算法

堆排序是一种基于堆数据结构的排序算法，它利用了堆的性质来进行排序。堆排序分为两个主要步骤：建堆和排序。

建堆：
首先，我们需要根据待排序的数组构建一个大根堆或小根堆。对于升序排序，我们需要构建一个大根堆；对于降序排序，我们需要构建一个小根堆。

大根堆的性质是：节点的值大于或等于其子节点的值。
小根堆的性质是：节点的值小于或等于其子节点的值。

构建大根堆的过程如下：

public static void buildHeap(int[] array, int length) {
    for (int i = length / 2 - 1; i >= 0; i--) {
        heapify(array, length, i);
    }
}

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

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

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

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

排序：
构建好大根堆之后，我们需要将堆顶元素与数组的最后一个元素进行交换，并且缩小堆的范围，然后再对堆进行堆化操作，重复此过程直到堆为空。最后得到的数组就是有序的。

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

    buildHeap(array, length);

    for (int i = length - 1; i >= 0; i--) {
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;

        heapify(array, i, 0);
    }
}

使用示例：

public static void main(String[] args) {
    int[] array = {4, 10, 3, 5, 1};
    heapSort(array);

    System.out.println(Arrays.toString(array));
}

输出结果为：[1, 3, 4, 5, 10]，即为升序排序的结果。

堆排序的时间复杂度为O(nlogn)，其中n为待排序元素的个数。堆排序是一种稳定的排序算法，适用于大规模数据的排序。