堆排序算法¶

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)

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)

    return arr

# 测试
arr = [5, 3, 8, 4, 2]
sorted_arr = heap_sort(arr)
print("排序后的数组:", sorted_arr)

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        heapSort(arr);
        System.out.println("排序后的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    public static void heapSort(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--) {
            // 将当前根节点移到末尾
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 对剩余的堆进行堆化
            heapify(arr, i, 0);
        }
    }

    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) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // 递归地对受影响的子树进行堆化
            heapify(arr, n, largest);
        }
    }
}