Java堆排序算法详解

Java堆排序（Heap Sort）算法是一种高效的排序算法，其时间复杂度为 $O(nlogn)$。该算法使用了最大堆或最小堆来进行排序，具有不占用额外空间、稳定性好等特点。下面我们将详细介绍Java堆排序算法的完整攻略。

1. 堆定义与性质

在Java堆排序算法中，使用的堆是一种完全二叉树，并且堆中的每个节点都大于等于（最大堆）或小于等于（最小堆）其子节点。因此，根节点对于整个堆来说一定是最大或最小的节点。

2. 堆排序流程

Java堆排序算法的具体执行过程可以分为以下步骤：

1. 建立堆。

首先，将待排序的数组看作完全二叉树，按照从下至上、从右至左的顺序，依次将所有非叶子节点调整为符合堆定义的最大堆或最小堆。

1. 将堆中的最大或最小值与末尾元素进行交换。

此时，我们将堆中的最大或最小值移动到了数组的末尾，该元素已经排序完成。然后，我们将堆中的最后一个元素（即此时数组中的最后一个元素）移到堆顶，并删掉该节点。接下来，再依次调整剩余的节点使其符合堆定义。

1. 重复步骤2，直到整个数组都被排序完成。

3. Java堆排序的代码实现

下面我们可以对Java堆排序的代码进行实现。假设我们需要对以下数组进行排序：

int[] array = { 3, 1, 5, 2, 7, 9, 4, 6, 8, 0 };

3.1 建堆

首先，我们需要建立一个最大堆。我们可以使用递归的方式进行建堆，代码如下：

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

    int largest = i;

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

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

    if (largest != i) {
        swap(array, i, largest);
        maxHeapify(array, largest, heapSize);
    }
}

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

    for (int i = (heapSize / 2) - 1; i >= 0; i--) {
        maxHeapify(array, i, heapSize);
    }
}

在这段代码中，maxHeapify函数调整一个节点和其子节点，使其符合最大堆的定义。buildMaxHeap函数则根据调整后的节点建立最大堆。

3.2 堆排序

接下来，我们需要进行堆排序的操作，代码如下：

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

    buildMaxHeap(array);

    for (int i = array.length - 1; i >= 1; i--) {
        swap(array, 0, i);
        heapSize--;
        maxHeapify(array, 0, heapSize);
    }
}

在这段代码中，我们首先使用buildMaxHeap函数建立最大堆，然后利用循环不断进行交换和调整节点的操作，直到数组有序。

4. Java堆排序的示例说明

示例1

假设我们需要对以下数组进行排序：

int[] array = { 3, 1, 5, 2, 7, 9, 4, 6, 8, 0 };

使用Java堆排序算法进行重排，可以得到排序后的数组：

int[] sortedArray = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

示例2

以下是另一个示例。假设我们需要对以下数组进行排序：

int[] array = { 1, 2, 2, 4, 5, 8, 10, 15, 22, 22, 23 };

使用Java堆排序算法进行重排，可以得到排序后的数组：

int[] sortedArray = { 1, 2, 2, 4, 5, 8, 10, 15, 22, 22, 23 };

可以看到，在第二个示例中询求堆排的结果并不需要调整原序列顺序，这也印证了Java堆排序的稳定性好的特点。

以上就是Java堆排序算法的详细攻略。