十大经典排序算法之一--------------堆排序(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

相关文章

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Tomcat版本与Java版本的关系及说明

《Tomcat版本与Java版本的关系及说明》:本文主要介绍Tomcat版本与Java版本的关系及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat版本与Java版本的关系Tomcat历史版本对应的Java版本Tomcat支持哪些版本的pythonJ

springboot security验证码的登录实例

《springbootsecurity验证码的登录实例》:本文主要介绍springbootsecurity验证码的登录实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录前言代码示例引入依赖定义验证码生成器定义获取验证码及认证接口测试获取验证码登录总结前言在spring

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s