十大经典排序算法之一--------------堆排序(java详解)

2024-02-19 03:36

本文主要是介绍十大经典排序算法之一--------------堆排序(java详解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一.堆排序基本介绍:

  1. 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。
  2. 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
  3. 每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆

 大顶堆&&小顶堆(图解):

  大顶堆:

 其中,二叉树节点外面标注的是堆对应的数组下标,也就是:

小顶堆:

*假设我们有了一个待排序的数组,并且构建好了他的逻辑结构,怎么能通过孩子找到双亲,或者通过双亲找到左右孩子呢?其实也很好理解,我们拿一颗二叉树出来就能很轻易的得出公式:

具体公式:  parent = (child - 1) / 2 ;

                   leftchild = parent * 2 + 1 ;

                   rightchild = parent * 2 + 2 ;

                   rightchild = leftchild + 1;

 二.堆排序详解:

2.1.堆排序的基本思路(这里以顺序排序为主):

  1. 将待排序序列构造成一个大顶堆
  2. 此时,整个序列的最大值就是堆顶的根节点
  3. 将其与末尾元素进行交换,此时末尾就为最大值
  4. 然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了

 ①.构建大顶堆:

1).以给定的无序堆为例:

2).此时我们从最后一个非叶子节点开始(叶子节点自然不用调整,最后一个非叶子节点为:

 arr.length / 2 - 1;也就是下面的6节点 ),从左至右,从上至下进行调整:

 3).找到第二个非叶节点4,由于【4,9,8】中9最大,4和9交换:

 4).这时,交换导致了子根【4,5,6】结构混乱(因为我们要建立的是大顶堆),继续调整,【4,5,6】中6最大,交换4和6:

此时,我们就将一个无序序列构造成了一个大顶堆 

建大堆代码实现:

	//将一个数组(二叉树), 调整成一个大顶堆/*** @param arr 待调整的数组* @param i 表示非叶子结点在数组中索引* @param length 表示对多少个元素继续调整, length 是在逐渐的减少*/public  static void adjustHeap(int arr[], int i, int length) {int temp = arr[i];//先取出当前元素的值,保存在临时变量//开始调整//说明//1. k = i * 2 + 1 k 是 i结点的左子结点for(int k = i * 2 + 1; k < length; k = k * 2 + 1) {if(k+1 < length && arr[k] < arr[k+1]) { //说明左子结点的值小于右子结点的值k++; // k 指向右子结点}if(arr[k] > temp) { //如果子结点大于父结点arr[i] = arr[k]; //把较大的值赋给当前结点i = k; //!!! i 指向 k,继续循环比较} else {break;//!}}//当for 循环结束后,我们已经将以i 为父结点的树的最大值,放在了 最顶(局部)arr[i] = temp;//将temp值放到调整后的位置}

②.将堆顶元素与末尾元素进行交换,使末尾元素最大,然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素,如此反复,重建,交换:

1).将堆顶元素9和末尾元素4进行交换:

 2).重新构建堆,使其继续满足堆的定义(除去9的数组建堆):

3).后续过程,继续进行调整,交换,如此反复进行,最终使得整个序列有序:

 

到这里你想必也能理解为什么是建大堆而不是小堆了吧,这个排序(顺序)过程实际就是利用堆顶的元素最大,使其和最后n-1个元素进行交换(数组的大小是逐渐缩小的),最终使得整个序列有序 

heapSort方法实现:

	//编写一个堆排序的方法public static void heapSort(int arr[]) {int temp = 0;//将无序序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆,这里是建大堆for(int i = arr.length / 2 -1; i >=0; i--) {adjustHeap(arr, i, arr.length);}/** 2).将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;3).重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。*/for(int j = arr.length-1;j >0; j--) {//交换temp = arr[j];arr[j] = arr[0];arr[0] = temp;adjustHeap(arr, 0, j); }//System.out.println("数组=" + Arrays.toString(arr)); }

 堆排序完整代码:

import java.util.*;
public class HeapSort {
//测试数据public static void main(String[] args){int[] arr = {4,6,8,5,9};heapSort(arr);System.out.println("堆排序:"+Arrays.toString(arr));}public static void heapSort(int[] arr){int temp = 0;for(int i = arr.length / 2 - 1;i >= 0;i--){adjustHeap(arr,i,arr.length);}for(int j = arr.length - 1;j > 0;j--){temp = arr[j];arr[j] = arr[0];arr[0] = temp;adjustHeap(arr,0,j);}}public static void adjustHeap(int[] arr,int i,int length){int temp = arr[i];for(int k = 2 * i + 1;k < length;k = k * 2 + 1){if(k + 1 < length && arr[k] < arr[k+1]){k++;}if(arr[k] > temp){arr[i] = arr[k];i = k;}else{break;}}arr[i] = temp;}
}

运行结果:

 很明显,排序成功

堆排序速度测试:

 public static void main(String[] args){// 创建要给8000000个的随机的数组int[] arr = new int[8000000];for (int i = 0; i < 8000000; i++) {arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数}System.out.println("排序前");Date data1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String date1Str = simpleDateFormat.format(data1);System.out.println("排序前的时间是=" + date1Str);heapSort(arr);Date data2 = new Date();String date2Str = simpleDateFormat.format(data2);System.out.println("排序前的时间是=" + date2Str);}

 这里给8000000个数组排序,只用了2秒左右,可以看出堆排序的效率是相当的高

小结:

堆排序是一种基于二叉堆数据结构的排序算。它的主要思想是将待排序的元素构建成一个最大堆(或最小堆),然后依次将堆顶元素与堆的最后一个元素交换,并重新调整堆,使得剩余元素仍然满足堆的性质。重复这个过程,直到所有元素都被排序。

堆排序的步骤如下:

  1. 构建最大堆:将待排序的数组看作是一个完全二叉树,从最后一个非叶子节点开始,依次向上调整每个节点,使得每个节点都满足最大堆的性质。
  2. 交换堆顶元素和最后一个元素:将堆顶元素与堆的最后一个元素交换位置,此时最大元素已经排好序。
  3. 调整堆:将剩余元素重新调整为最大堆,再次找到最大元素并交换到堆顶。
  4. 重复步骤2和步骤3,直到所有元素都被排序。

堆排序的时间复杂度为O(nlogn),其中n为待排序数组的长度。它是一种不稳定的排序算法,因为在调整堆的过程中可能会改变相同元素的相对顺序。

博客到这里也是结束了,制作不易,喜欢的小伙伴可以点赞加关注支持下博主,这对我真的很重要~~

 

这篇关于十大经典排序算法之一--------------堆排序(java详解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/723371

相关文章

Linux换行符的使用方法详解

《Linux换行符的使用方法详解》本文介绍了Linux中常用的换行符LF及其在文件中的表示,展示了如何使用sed命令替换换行符,并列举了与换行符处理相关的Linux命令,通过代码讲解的非常详细,需要的... 目录简介检测文件中的换行符使用 cat -A 查看换行符使用 od -c 检查字符换行符格式转换将

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Springboot @Autowired和@Resource的区别解析

《Springboot@Autowired和@Resource的区别解析》@Resource是JDK提供的注解,只是Spring在实现上提供了这个注解的功能支持,本文给大家介绍Springboot@... 目录【一】定义【1】@Autowired【2】@Resource【二】区别【1】包含的属性不同【2】@

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

Elasticsearch 在 Java 中的使用教程

《Elasticsearch在Java中的使用教程》Elasticsearch是一个分布式搜索和分析引擎,基于ApacheLucene构建,能够实现实时数据的存储、搜索、和分析,它广泛应用于全文... 目录1. Elasticsearch 简介2. 环境准备2.1 安装 Elasticsearch2.2 J

详解C#如何提取PDF文档中的图片

《详解C#如何提取PDF文档中的图片》提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使用,下面我们就来看看如何使用C#通过代码从PDF文档中提取图片吧... 当 PDF 文件中包含有价值的图片,如艺术画作、设计素材、报告图表等,提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain