【算法】堆排序的原理与Java实现

简介: 堆排序(Heap Sort)是一种基于堆数据结构的排序算法。堆是一种完全二叉树,其中父节点的值总是大于(或小于)其子节点的值。堆排序的基本思想是先将待排序的数组构建成一个最大堆(或最小堆),然后重复从堆顶取出最大(或最小)元素,放到已排序的部分,再调整剩余元素构建新的堆,直到所有元素都被放置到正确的位置。

一.堆排序原理


堆排序(Heap Sort)是一种基于堆数据结构的排序算法。堆是一种完全二叉树,其中父节点的值总是大于(或小于)其子节点的值。堆排序的基本思想是先将待排序的数组构建成一个最大堆(或最小堆),然后重复从堆顶取出最大(或最小)元素,放到已排序的部分,再调整剩余元素构建新的堆,直到所有元素都被放置到正确的位置。


堆排序的具体步骤如下:

1.构建最大堆(或最小堆):将待排序的数组看作是一个完全二叉树,并从最后一个非叶子节点开始,自底向上地调整每个节点,使其满足堆的性质。这一步骤保证了最大堆(或最小堆)的构建。

2.取出堆顶元素:将堆顶元素(最大元素或最小元素)与堆中最后一个元素交换位置,并将堆的大小减一。

3.调整堆:将堆顶元素下沉至合适的位置,保持堆的性质。这一步骤重新构建了最大堆(或最小堆)。

4.重复步骤2和步骤3,直到堆为空。


二.使用Java实现堆排序


public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 3, 1};
        System.out.println("Before sorting:");
        printArray(arr);
        heapSort(arr);
        System.out.println("After sorting:");
        printArray(arr);
    }
    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);
        }
    }
    public static void heapify(int[] arr, int n, int i) {
        int largest = i; // 当前节点的索引
        int leftChild = 2 * i + 1; // 左子节点的索引
        int rightChild = 2 * i + 2; // 右子节点的索引
        // 如果左子节点大于父节点,更新最大节点的索引
        if (leftChild < n && arr[leftChild] > arr[largest]) {
            largest = leftChild;
        }
        // 如果右子节点大于父节点,更新最大节点的索引
        if (rightChild < n && arr[rightChild] > arr[largest]) {
            largest = rightChild;
        }
        // 如果最大节点不是当前节点,交换节点的位置并继续调整堆
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

以上代码使用堆排序算法对一个整数数组进行排序。heapSort方法实现了堆排序的逻辑,首先构建最大堆,然后重复从堆顶取出最大元素,放到已排序的部分,并调整剩余元素构建新的堆,直到所有元素都被放置到正确的位置。heapify方法用于调整堆,保持最大堆性质。


运行以上代码,将输出如下结果:

Before sorting:
5 2 8 3 1 
After sorting:
1 2 3 5 8

堆排序算法的时间复杂度为O(nlogn),其中n是数组的长度。它是一种不稳定的排序算法,适用于任何规模的数组。堆排序在实现上相对较复杂,但由于其在原地排序的特性,对于大规模数据的排序效果较好。

相关文章
|
11天前
|
存储 算法 搜索推荐
软考算法破壁战:从二分查找到堆排序,九大排序核心速通指南
专攻软考高频算法,深度解析二分查找、堆排序、快速排序核心技巧,对比九大排序算法,配套动画与真题,7天掌握45%分值模块。
64 0
软考算法破壁战:从二分查找到堆排序,九大排序核心速通指南
机器学习/深度学习 算法 自动驾驶
113 0
|
20天前
|
机器学习/深度学习 算法 搜索推荐
从零开始构建图注意力网络:GAT算法原理与数值实现详解
本文详细解析了图注意力网络(GAT)的算法原理和实现过程。GAT通过引入注意力机制解决了图卷积网络(GCN)中所有邻居节点贡献相等的局限性,让模型能够自动学习不同邻居的重要性权重。
92 0
从零开始构建图注意力网络:GAT算法原理与数值实现详解
|
28天前
|
机器学习/深度学习 算法 文件存储
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
神经架构搜索(NAS)正被广泛应用于大模型及语言/视觉模型设计,如LangVision-LoRA-NAS、Jet-Nemotron等。本文回顾NAS核心技术,解析其自动化设计原理,探讨强化学习、进化算法与梯度方法的应用与差异,揭示NAS在大模型时代的潜力与挑战。
256 6
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
|
1月前
|
传感器 算法 定位技术
KF,EKF,IEKF 算法的基本原理并构建推导出四轮前驱自主移动机器人的运动学模型和观测模型(Matlab代码实现)
KF,EKF,IEKF 算法的基本原理并构建推导出四轮前驱自主移动机器人的运动学模型和观测模型(Matlab代码实现)
|
1月前
|
算法
离散粒子群算法(DPSO)的原理与MATLAB实现
离散粒子群算法(DPSO)的原理与MATLAB实现
86 0
|
2月前
|
监控 Java API
现代 Java IO 高性能实践从原理到落地的高效实现路径与实战指南
本文深入解析现代Java高性能IO实践,涵盖异步非阻塞IO、操作系统优化、大文件处理、响应式网络编程与数据库访问,结合Netty、Reactor等技术落地高并发应用,助力构建高效可扩展的IO系统。
88 0
|
2月前
|
机器学习/深度学习 人工智能 编解码
AI视觉新突破:多角度理解3D世界的算法原理全解析
多视角条件扩散算法通过多张图片输入生成高质量3D模型,克服了单图建模背面细节缺失的问题。该技术模拟人类多角度观察方式,结合跨视图注意力机制与一致性损失优化,大幅提升几何精度与纹理保真度,成为AI 3D生成的重要突破。
172 0
|
2月前
|
存储 缓存 安全
深入讲解 Java 并发编程核心原理与应用案例
本教程全面讲解Java并发编程,涵盖并发基础、线程安全、同步机制、并发工具类、线程池及实际应用案例,助你掌握多线程开发核心技术,提升程序性能与响应能力。
111 0