Java详细讲解堆排序与时间复杂度的概念

2024-10-01 16:48:38

一、堆排序

1、什么是堆排序

（1）堆排序：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

（2）堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

2、堆排序思想

（1）将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆

（2）将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端

（3）重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序

3、代码实现

import java.util.Arrays;
public class Sort {
     //将任意数组进行原地堆排序
    public static void heapSort(int[] arr) {
        //把数组调整为最大堆，从最后一个非叶子节点开始下沉
        for (int i = (arr.length-1-1)/2; i >= 0; i--) {
            siftDown(arr,i,arr.length);
        }
        //将堆顶元素和最后一个元素交换
        for (int i = arr.length-1; i > 0 ; i--) {
            swap(arr,0,i);
            siftDown(arr,0,i);
        }
    }
   //下沉操作
    private static void siftDown(int[] arr, int i, int n) {
        while ((2 * i)+1 < n){
            int j = (2 * i) + 1;
            if(j+1<n && arr[j+1]>arr[j]){
               j = j+1;
            }
            if(arr[i] >= arr[j]){
                break;
            }else{
                swap(arr,i,j);
                i = j;
            }
        }
    }
     public static void main(String []args){
        int []arr = {7,6,7,11,5,12,3,0,1};
        System.out.println("排序前："+ Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后："+Arrays.toString(arr));
    }
}

运行截图：

二、时间复杂度分析

1、初始化建堆

初始化建堆只需要对二叉树的非叶子节点由下至上，由右至左选取非叶子节点来调用adjusthead()函数。那么倒数第二层的最右边的非叶子节点就是最后一个非叶子结点。

　假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。高层也是这样逐渐递归。

　那么总的时间计算为：s = 2^( i - 1 ) * ( k - i )；其中 i 表示第几层，2^( i - 1) 表示该层上有多少个元素，( k - i) 表示子树上要下调比较的次数。

S = n - log(n) -1，所以时间复杂度为：O(n)

2、排序重建堆

每次重建意味着有一个节点出堆，所以需要将堆的容量减一。adjustheap()函数的时间复杂度k=log(n)，k为堆的层数。所以在每次重建时，随着堆的容量的减小，层数会下降，函数时间复杂度会变化。重建堆一共需要n-1次循环，每次循环的比较次数为log(i)，则相加为：log2+log3+…+log(n-1)+log(n)≈log(n!)。

所以时间复杂度为O(nlogn)

3、总结

初始化建堆的时间复杂度为O(n)，排序重建堆的时间复杂度为nlog(n)，所以总的时间复杂度为O(nlogn)，空间复杂度为O（1）。

到此这篇关于Java详细讲解堆排序与时间复杂度的概念的文章就介绍到这了,更多相关Java堆排序与时间复杂度内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

详解如何在Java中实现堆排序算法

目录算法描述实现代码测试代码算法描述堆排序算法的描述如下: 将待排序的数组调整为最大堆,此时未排序的长度 N 为数组的长度,调整的过程就是倒序将数组的前 N/2 个元素下沉的过程,每次下沉都会将较大的元素带到上面,最终将数组变为最大堆: 弹出最大堆的堆顶元素并将其移动到数组的最后面,将原本最后面的元素放到堆顶,然后将未排序的长度 N - 1,调整数组的前 N 个元素为最大堆: 重复步骤 2 直到未排序的长度为 0. 实现代码 package com.zhiyiyo.collection
java实现堆排序以及时间复杂度的分析

完全二叉树:从上到下,从左到右,每层的节点都是满的,最下边一层所有的节点都是连续集中在最左边. 二叉树的特点就是左子节点是父节点索引值的2倍加一,右子节点是父节点索引值的2倍加二堆分为两种:大顶堆和小顶堆大顶堆:在完全二叉树基础上,每个节点的值都大于或等于其左右子节点的值小顶堆:在完全二叉树基础上,每个节点的值都大于或等于其左右子节点的值堆排序就是根据先构建好的大顶堆或小顶堆进行排序的. 怎么构建大顶堆: 假如一个数组是:int[] arr
Java 数据结构与算法系列精讲之时间复杂度与空间复杂度

目录概述算法的衡量标准时间复杂度最优时间复杂度平均时间复杂度最坏时间复杂度 O(1) O(n) O(n^2) O(logN) 空间复杂度 O(1) O(n) 概述从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 算法的衡量标准当我们需要衡量一个算法的的优越性, 通常会使用时间复杂度 (Time Complexity) 和空间复杂度 (Space Complexity) 来衡量. 时间复杂度时间复杂度 (Time Complexity) 通常用 O(n)
JAVA堆排序算法的讲解

预备知识堆排序堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序.首先简单了解下堆结构. 堆堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆:或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆.如下图: 同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面这个样子该数组从逻辑上讲就是一个堆结构,我们用简单的公式来描述一下堆的定义就是: 大顶
Java 精炼解读时间复杂度与空间复杂度

目录前言: 一.算法效率二.时间复杂度 1.时间复杂度概念 2.大O的渐进表示法计算时间复杂度三.空间复杂度总结: 前言: 所谓的复杂度就是衡量算法的效率,衡量算发效率又分为两种,一种叫做时间复杂度,一种叫做空间复杂度. 一.算法效率算法效率分析分为两种:第一种是时间效率,第二种是空间效率.时间效率被称为时间复杂度,而空间效率被称作空间复杂度. 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间,在计算机发展的早期,计算机的存储容量很小.所以对
Java 十大排序算法之堆排序刨析

二叉堆是完全二叉树或者是近似完全二叉树. 二叉堆满足二个特性︰ 1．父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值. 2．每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆). 任意节点的值都大于其子节点的值--大顶堆(最后输出从小到大排) 任意节点的值都小于其子节点的值---小顶堆(最后输出从大到小排) 堆排序步骤 1.堆化,反向调整使得每个子树都是大顶或者小顶堆(建堆) 2.按序输出元素∶把堆顶和最末元素对调,然后调整堆顶元素(排序) 堆排序代码实现(大顶堆) publ
JAVA十大排序算法之堆排序详解

目录堆排序知识补充二叉树满二叉树完全二叉树二叉堆代码实现时间复杂度算法稳定性思考总结堆排序这里的堆并不是JVM中堆栈的堆,而是一种特殊的二叉树,通常也叫作二叉堆.它具有以下特点: 它是完全二叉树堆中某个结点的值总是不大于或不小于其父结点的值知识补充二叉树树中节点的子节点不超过2的有序树满二叉树二叉树中除了叶子节点,每个节点的子节点都为2,则此二叉树为满二叉树. 完全二叉树如果对满二叉树的结点进行编号,约定编号从根结点起,自上而下,自左而右.则深度为k的,有
图解Java排序算法之堆排序

目录预备知识堆排序堆堆排序基本思想及步骤再简单总结下堆排序的基本思路: 总结预备知识堆排序堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序.首先简单了解下堆结构. 堆堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆:或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆.如下图: 同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面
Java详细讲解堆排序与时间复杂度的概念

目录一.堆排序 1.什么是堆排序 2.堆排序思想 3.代码实现二.时间复杂度分析 1.初始化建堆 2.排序重建堆 3.总结一.堆排序 1.什么是堆排序 (1)堆排序:堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法.堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点. (2)堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆:或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆
Java 详细讲解用堆解决Top-k问题

目录 1.什么是堆? 堆结构大根堆 VS 小根堆大根堆(最大堆) 小根堆(最小堆) 优先级队列(PriorityQueue) 2.top-k问题解决思路要解决 top-k 问题,我们应该先熟悉一种数据结构 - 堆(优先级队列),已经了解的朋友可以跳过哦. 1.什么是堆? 堆结构堆其实就是一种二叉树,但是普通的二叉树是以链式结构进行储存数据的,而堆是以数组进行顺序存储数据的.那么什么样的二叉树才适合用顺序存储的方式呢? 我们假设一颗普通的二叉树可以用数组存储,那么就可以得到如下结构: 我们
C语言超详细讲解算法的时间复杂度和空间复杂度

目录 1.前言 1.1 什么是数据结构? 1.2 什么是算法? 2.算法效率 2.1 如何衡量一个算法的好坏 2.2 算法的复杂度 2.3 复杂度在校招中的考察 3.时间复杂度 3.1 时间复杂度的概念 3.2 大O的渐进表示法 3.3 常见时间复杂度计算举例 4.空间复杂度 5. 常见复杂度对比 1.前言 1.1 什么是数据结构? 数据结构(Data Structure)是计算机存储.组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合. 1.2 什么是算法? 算法(Algorit
Java详细讲解异常Exception的处理

目录 1.异常介绍 2.常见的运行时异常 1.空指针异常 2.数学运算异常 3.数组下标越界异常 4.类型转换异常 5.数字格式不正确异常 1.异常介绍基本概念程序执行中发生的不正常情况称为异常.(语法错误和逻辑错误不是异常). package com.demo; /** * @version 1.0 * @auther Demo龙 */ public class exception01 { public static void main(String[] args) { int num1
Java 详细讲解分治算法如何实现归并排序

目录 1.什么是分治算法分治法基本思想 2.分治算法的体现--归并排序归并排序基本思想 3.代码实现 1.什么是分治算法分治法分治法,字面意思是"分而治之",就是把一个复杂的1问题分成两个或多个相同或相似的子问题,再把子问题分成更小的子问题直到最后子问题可以简单地直接求解,原问题的解即子问题的解的合并,这个思想是很多高效算法的基础,例如排序算法(快速排序,归并排序),傅里叶变换(快速傅里叶变换)等. 基本思想分治法的基本思想:将一个难以直接解决的大问题,分割成一些规模较小
Java详细讲解不同版本的接口语法和抽象类与接口的区别

目录什么是接口? 接口的语法: (JDK7.0) 接口的语法: (JDK8.0) 接口的语法: (JDK9.0)—(私有方法) 接口的分类常量接口: 空接口: 函数式接口: 什么是接口? 说到接口,USB大家肯定不陌生~接口是一种标准.规范.注意:接口一旦制定好,使用者和实现者都必须遵循的标准. 接口的语法: (JDK7.0) (1) 关键字:interface (2) 语法: interface 接口名{} (3) 接口编译之后会生成对应的 .class文件 (4) 接口不能创建对象,但
Java 详细讲解线程安全与同步附实例与注释

目录线程安全问题实例: 存钱取钱问题买票问题线程安全问题分析问题解决方案线程同步同步语句 synchronize(obj)的原理同步方法同步方法的本质线程安全问题多个线程可能会共享(访问)同一个资源比如访问同一个对象,同一个变量,同一个文件当多个线程访问同一块资源时,很容易引发数据错乱和数据安全问题,称为线程安全问题什么情况下会出现线程安全问题多个线程共享同一个资源且至少有一个线程正在执行写的操作实例: 存钱取钱问题分别有存钱和取钱2个线程存钱
Java 详细讲解线程的状态及部分常用方法

可以通过 Thread.getState 方法获得线程的状态(线程一共有 6 种状态) NEW(新建)new:尚未启动 RUNNABLE(可运行状态)runnable:正在 JVM 中运行:或者正在等待操作系统的其他资源(比如处理器) //有些编程语言会把RUNNABLE分成2种情况//1.running//2.ready//以上2种在Java中都属于RUNNABLE BLOCKED(阻塞状态) blocked:正在等待监视器锁(内部锁) WAITING(等待状态) waiting:在等待另一个
Java 详细讲解线程的状态及部分常用方法

可以通过 Thread.getState 方法获得线程的状态(线程一共有 6 种状态) NEW(新建)new:尚未启动 RUNNABLE(可运行状态)runnable:正在 JVM 中运行:或者正在等待操作系统的其他资源(比如处理器) //有些编程语言会把RUNNABLE分成2种情况//1.running//2.ready//以上2种在Java中都属于RUNNABLE BLOCKED(阻塞状态) blocked:正在等待监视器锁(内部锁) WAITING(等待状态) waiting:在等待另一个
Java详细讲解分析双指针法的使用

目录前言 1.判断链表是否有环 2.查找链表中间的元素 3.奇偶排序前奇后偶 4.删除排序链表的重复元素 5.三数之和 6.分割链表 7.合并两个有序的数组 8.两数之和—输入有序数组 9.长度最小的子数组 10.排序链表前言通常用在线性的数据结构中,比如链表和数组. 指针其实就是数据的索引或者链表的结点.两个指针朝着左右两个方向移动,直到满足搜索条件. 双指针可分为同向双指针.异向双指针.快慢指针.滑动窗口.根据需求选择双指针的模型,比如删除数组或链表中重复的元素,同向双指针(线性表前