Java堆排序的算法及代码实现

涛哥
Java代码

堆排序是一种基于堆数据结构的排序算法，Java 堆排序的算法和代码实现如下：

  1. 算法原理

堆排序的核心是建立一个最大堆或最小堆，将堆顶元素交换到堆底，然后对剩余的元素重新维护最大堆或最小堆，重复执行这个过程直到所有元素都被排序。

  1. 代码实现

以下是 Java 堆排序的示例代码：

public class HeapSort {
    public void heapSort(int[] arr) {
        int len = arr.length;

        // 建立最大堆
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapify(arr, len, i);
        }

        // 交换堆顶和堆底元素，并重新维护最大堆
        for (int i = len - 1; i >= 0; i--) {
            swap(arr, 0, i);
            heapify(arr, i, 0);
        }
    }

    // 维护最大堆的过程
    public void heapify(int[] arr, int len, int i) {
        int largest = i; // 假设当前节点是最大的
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, len, largest);
        }
    }

    // 交换数组中的两个元素
    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 示例
    public static void main(String[] args) {
        int[] arr = { 3, 7, 4, 8, 6, 2, 1, 5 };
        HeapSort heapSort = new HeapSort();
        heapSort.heapSort(arr);
        System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8]
    }
}

在这个示例中，我们首先定义了一个 HeapSort 类，包含了 heapSort、heapify 和 swap 三个方法。其中 heapSort 方法用于进行堆排序，heapify 方法用于维护最大堆，swap 方法用于交换数组中的两个元素。

在 heapSort 方法中，我们首先建立最大堆，然后将堆顶元素和堆底元素交换，并重新维护最大堆，直到所有元素都被排序。

在 heapify 方法中，我们使用递归的方式维护最大堆。对于当前节点，我们先假设它是最大的，然后比较它和左右子节点的大小，如果存在比它更大的子节点，则将当前节点和子节点交换位置，并继续递归向下维护最大堆。

在 swap 方法中，我们使用一个临时变量来交换数组中的两个元素。

在示例的 main 方法中，我们定义一个待排序的数组，然后创建一个 HeapSort 对象，调用 heapSort 方法对数组进行排序，并使用 Arrays.toString() 方法打印排序后的数组。

  1. 时间复杂度

堆排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。堆排序的空间复杂度为 O(1)。

  1. 总结

堆排序是一种高效的排序算法，它的时间复杂度比较稳定，不受数据分布的影响，适用于大规模数据的排序。但是堆排序的代码实现比较复杂，需要熟悉堆数据结构和递归的思想。

 
  • 堆排序
  • 数组