Java基础算法之堆排序(Heap Sort) synchronized批量重偏向与批量撤销 终于等到了!阿里P8历时九个月整理,Java面试宝典,核心知识点笔记在此 “数字心脏”动态解析消费密码,国家级消费市场大数据联合实验室在上海先行先试 全世界运行着大约230亿台物联网设备,安全问题如何解? 物联网产业园&thinkplus解决方案中心国学讲座如期而至 都是程序员,凭什么他能站在鄙视链的顶端? 猛男必看!去小红书做程序员是种什么体验 drozer提示[Errno 2] No such file or directory 【STM32】NB-iOT BC35-G模块 AT指令应用设计指导(附代码) 【北京迅为】i.MX6ULL终结者编译LED汇编程序 Linux系统读写网卡PHY寄存器工具 洛谷:P1226 【模板】快速幂||取余运算(分治,数学) 【2020顶会KDD】AutoST:面向时空预测的高效神经网络学习模型 C/C++实现并查集disjoint_set的模板(带路径压缩优化) 实现一个百万级推送服务,除了它,还有谁 “健康守护者”——STM32标准库和HAL库的比较 程序员被公司辞退12天后,前领导要求回公司讲清代码,结果懵了 RTTR实现C++反射(1)集成rttr库 lotus node 远程运行 CCF历年4,5题收录 N卡 RTX3070/RTX3080/RTX3090挖矿算力推测 最高算力86MH 理论+实验:MySQL索引、事物与存储引擎 PostgreSQL JOIN 多表查询 TP框架实现Excel批量导入数据库数据 MySQL中的列转行 这次是真拯救了我,MySQL索引优化,explain讲得非常清楚了 Oracle快速入门(PLSQL编程) MySQL字符串拼接、截取 MySQL事务管理及存储引擎 《浪姐》万茜点赞宁静、郁可唯黑贴坐实?盗号者和程序员是背锅侠 程序员被公司辞退12天后,前领导要求回公司讲清代码,结果懵了 易语言大漠多线程foobar在游戏多窗口中时时显示输出信息 非科班,自学两年,复盘两个月,侥幸拿到头条、阿里offer 2020年全国数学建模大赛B题源代码以及模型的建立 (2) 2020年数学建模-校园供水系统智能管理 windows破解锁屏密码(亲测有效:再也不怕别人锁屏防你啦!) 清华大佬力荐的JVM学习路线+实战笔记+阿里真题,嚼碎吃透吊打面试官 打造多模块+高可用+高扩展Spring Cloud版分布式电商项目源码分享 Python爬虫入门教程 89-100 定个小目标,先用Python爬个一亿B站用户 五大分布式事务,你了解多少? 2020-09-12 九大核心专题,630页内容,熬夜23天吃透,我收割了3个大厂offer 防抖节流 防抖和节流 函数节流 debounce throttle 每天补充一点 一些零碎的小知识点 JavaScript作用域和作用域链知多少 01-jquery概述 简单概述JSONP原理 02-$符号-jquery与js相互转换 遇见 vue.js --------阿文的vue.js学习笔记(2)----- 基本使用
您的位置:首页 >前端 >

Java基础算法之堆排序(Heap Sort)

堆排序(Heap Sort)

1、堆介绍2、算法介绍3、图解4、代码实现5、执行结果6、其他算法

1、堆介绍

大顶堆: 非叶子结点的数据要大于或等于其左,右子节点的数据

小顶堆: 非叶子结点的数据要小于或等于其左,右子节点的数据

2、算法介绍

先从后面的非叶子结点从后向前将结点构建成一个大顶堆(小顶堆)。此时根节点就是最大的数据(最小的数据),然后将根节点与数组最后一位进行交换。交换后再从根节点开始构建堆(此时树的长度应该减一,因为最大的数已经确定了)。重复执行2-3步骤,直到数据有序。

3、图解

堆排序图解

4、代码实现

package sort;import java.util.Arrays;/** * <p> * * </p> * * @author: D * @since: 2020/9/11 * @version: 1 */public class HeapSortDemo {public static void main(String[] args) {int[] arr = {117, 101, 106, 100, 112, 60, 90, 110};heapSort(arr);Arrays.sort(arr);System.out.println(Arrays.toString(arr));}private static void heapSort(int[] arr) {int temp;System.out.println("从后向前构建堆");//从后面的非叶子结点进行调整数组为大顶堆for (int i = arr.length / 2 - 1; i >= 0; i--) {System.out.println("非叶子结点:" + i);bigTopPile(arr, i, arr.length);}System.out.println("从根节点开始构建堆");for (int j = arr.length - 1; j > 0; j--) {temp = arr[j];arr[j] = arr[0];arr[0] = temp;System.out.println("确认下标为" + j + ":" + Arrays.toString(arr));// 从根节点开始调整数据为大顶堆bigTopPile(arr, 0, j);}}/** * 将数组变为一个大顶堆 * * @param arr 数组 * @param nonLeafNode 非叶子结点在数组中的下标 * @param length调整的数组长度 */private static void bigTopPile(int[] arr, int nonLeafNode, int length) {System.out.println("构建前数组:" + Arrays.toString(arr));//保存非叶子结点int temp = arr[nonLeafNode];System.out.println("非叶子结点数据:" + temp);// index = nonLeafNode * 2 + 1 index为非叶子结点的左子结点for (int index = nonLeafNode * 2 + 1; index < length; index = index * 2 + 1) {System.out.println("左子节点:" + index);//左子节点小于右子节点右子节点就是左子节点加1if (index + 1 < length && arr[index] < arr[index + 1]) {System.out.println("左子节点小于右子节点,指针指向右子节点");//左子节点小于右子节点 那么将index此时指向右子节点index++;}//如果子节点大于父节点则进行交换if (arr[index] > temp) {System.out.println("子节点大于父节点,进行交换");arr[nonLeafNode] = arr[index];nonLeafNode = index;} else {break;}}arr[nonLeafNode] = temp;System.out.println("构建后数组:" + Arrays.toString(arr));System.out.println();}}

5、执行结果

image-20200911104430539

image-20200911104458365

image-20200911104513701

6、其他算法

选择排序(Selection Sort) 插入排序(Insertion Sort) 希尔排序(Shell Sort) 冒泡排序(Bubble Sort) 快速排序(Quick Sort)

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。