Java算法之堆排序代码示例

下面是Java算法之堆排序代码示例的完整攻略：

堆排序算法概述

堆排序是一种利用堆的数据结构所设计的一种基于选择的排序算法。堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。

基本思想是：

1. 将待排序序列构造成一个堆（大根堆或小根堆）；
2. 将根节点与最后一个节点交换，将交换后的最后一个节点从堆中排除；
3. 对剩余元素重新建堆，重复步骤2，直至剩余元素个数为1。

Java实现

下面给出Java实现堆排序的代码示例：

public class HeapSort {
    public static void heapSort(int[] arr) {
        int length = arr.length;
        // 构造初始堆
        for (int i = length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, length);
        }
        // 交换堆顶元素和最后一个元素，取出当前最大元素
        for (int i = length - 1; i >= 0; i--) {
            swap(arr, 0, i);
            adjustHeap(arr, 0, i);
        }
    }

    // 调整堆
    public static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            if (arr[k] > temp) {
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }
        arr[i] = temp;
    }

    // 交换数组中两个下标对应的元素
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = { 10, 5, 2, 3, 9, 6, 11 };
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

上面的代码使用了两个方法来实现堆排序：heapSort和adjustHeap。

其中，heapSort方法调用adjustHeap方法来构造堆和调整堆的过程。在heapSort方法中，首先构造初始堆，然后每次交换堆顶元素和最后一个元素，并继续调整堆。

adjustHeap方法实现堆的调整，传入的参数i是需要调整的父节点，length是当前堆的长度。堆的调整是递归实现的，其中，temp保存需要调整的父节点的值，k是左子节点的下标。如果右子节点也存在，并且右子节点的值大于左子节点的值，则k指向右子节点，否则k指向左子节点。如果节点k的值大于父节点i的值，则将节点k种的值赋值给节点i，并更新i的值为k的值，继续递归调整。

示例说明

下面给出两个示例说明：

示例一

假设有一个数组arr，其元素为{10, 5, 2, 3, 9, 6, 11}，我们希望对其进行排序。我们可以通过调用heapSort方法，来实现对该数组的排序。

int[] arr = { 10, 5, 2, 3, 9, 6, 11 };
heapSort(arr);
System.out.println(Arrays.toString(arr));

输出结果为：[2, 3, 5, 6, 9, 10, 11]。

示例二

假设有一个数组arr，其元素为{43, 12, 67, 45, 21, 34}，我们希望对其进行排序。我们可以通过调用heapSort方法，来实现对该数组的排序。

int[] arr = { 43, 12, 67, 45, 21, 34 };
heapSort(arr);
System.out.println(Arrays.toString(arr));

输出结果为：[12, 21, 34, 43, 45, 67]。

以上就是Java算法之堆排序代码示例的完整攻略，包含了堆排序算法的概述、Java实现、以及两个示例说明。