JAVA堆排序算法的讲解

算法简介

堆排序（Heap Sort）是一种选择排序，它的主要思想是将待排序序列构建成一个大顶堆或小顶堆，然后将堆顶元素与最后一个元素交换位置，再对剩余 n - 1 个元素进行同样的操作，依次类推，直到整个序列有序。

堆排序的时间复杂度为 O(nlogn)，是一种比较高效的排序算法。

算法步骤

1. 对待排序的序列进行堆的构建，构建出一个大顶堆或小顶堆；
2. 构建出堆后，堆顶元素一定是最大或最小的元素，将其与序列的最后一个元素进行交换；
3. 排除掉已经排好序的最后一个元素，对剩余元素重新构建堆，重复步骤2和3，直到所有元素都已经排好序。

代码实现

JAVA 代码实现

/**
 * 堆排序算法
 * 时间复杂度：O(nlogn)
 */
public class HeapSort {

    public static void sort(int[] arr) {
        int n = arr.length;

        // 构建大顶堆，从最后一个非叶子节点开始向下调整
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // 将堆顶元素与序列最后一个元素交换位置，然后对剩余元素重新构建堆
        for (int i = n - 1; i >= 0; i--) {
            swap(arr, 0, i);
            heapify(arr, i, 0);
        }
    }

    /**
     * 将以i为根节点的子树调整成大顶堆
     * @param arr 数组
     * @param n 数组长度
     * @param i 根节点位置
     */
    private static void heapify(int[] arr, int n, int i) {
        int largest = i; // 根节点
        int left = 2 * i + 1; // 左子节点
        int right = 2 * i + 2; // 右子节点

        // 找到最大的节点
        if (left < n && arr[left] > arr[largest])
            largest = left;
        if (right < n && arr[right] > arr[largest])
            largest = right;

        // 如果最大节点不是根节点，那么把最大节点与根节点交换，然后继续向下递归调整
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, n, largest);
        }
    }

    /**
     * 交换数组中的两个元素
     * @param arr 数组
     * @param i 元素1的位置
     * @param j 元素2的位置
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Python 代码实现

def heap_sort(arr):
    n = len(arr)

    # 构建大顶堆，从最后一个非叶子节点开始向下调整
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 将堆顶元素与序列最后一个元素交换位置，然后对剩余元素重新构建堆
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

def heapify(arr, n, i):
    largest = i # 根节点
    left = 2 * i + 1 # 左子节点
    right = 2 * i + 2 # 右子节点

    # 找到最大的节点
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 如果最大节点不是根节点，那么把最大节点与根节点交换，然后继续向下递归调整
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

示例

示例1

排序前的数组：[5, 3, 8, 4, 7, 2, 6, 1]

排序后的数组：[1, 2, 3, 4, 5, 6, 7, 8]

示例2

排序前的数组：[99, 0, 33, 46, 12, 78, 21, 5]

排序后的数组：[0, 5, 12, 21, 33, 46, 78, 99]

总结

堆排序算法是一种高效的排序算法，适用于大规模数据的排序。它通过构建大顶堆或小顶堆，实现了对序列的快速排序。堆排序可以通过数组实现，也可以通过树实现。