Java详细讲解堆排序与时间复杂度的概念
作者:淡沫初夏Zz 发布时间:2023-10-20 02:00:11
一、堆排序
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)。
来源:https://blog.csdn.net/qq_55660421/article/details/122380669
猜你喜欢
- 什么是OKHttp一般在Java平台上,我们会使用Apache HttpClient作为Http客户端,用于发送 HTTP 请求,并对响应进
- 实现原理: 长连接的维持,是要客户端程序,定时向服务端程序,发送一个
- .c 源程序 ----- 编译 ----- 链接 ---- exe ----运行 -------->程序翻译环境和执行环境翻译环境:源
- 合成聚合复用原则合成复用原则又称为组合/聚合复用原则(Composition/Aggregate Reuse Principle, CARP
- Note:这篇文章是基于Android Studio 3.01版本的,NDK是R16。step1:创建一个包含C++的项目其他默认就可以了。
- Android权限一般是在AndroidManifest.xml中声明,在安装或首次使用的时候系统会自动提示用户是否提供权限Android官
- 一、@Value读取application.properties配置文件中的值application.properties配置文件fileN
- 在我们实现某些功能时,可能会有倒计时的需求。比如发送短信验证码,发送成功后可能要求用户一段时间内不能再次发送,这时候我们就需要进行倒计时,时
- 如果想实现一个在桌面显示的悬浮窗,用Dialog、PopupWindow、Toast等已经不能实现了,他们基本都是在Activity之上显示
- 前言二进制文件读写两个重要的函数 , fread 和 fwrite , fread 用于读取文件 , fwrite 用于写出文件 ;frea
- instanceof判断某个对象是否是某个类的实例或者某个类的子类的实例。它的判断方式大概是这样的:public<T> bool
- 参数和返回值得加密目的为了保证接口不被人拦截下来恶意请求,保证程序的稳定性,我们可以使用接口加密的方法来保证参数和返回值的保密性。具体实现方
- 在程序中封装了一个List集合对象,然后需要把该集合中的实体插入到数据库中,由于项目使用了Spring+MyBatis的配置,所以打算使用M
- 一、链表的介绍什么是链表链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结
- 什么是FTPFTP(File Transfer Protocol)是TCP/IP网络上两台计算机传送文件的协议,使得主机间可以共享文件.可以
- 错误处理到目前为止,我们都没怎么介绍onComplete()和onError()函数。这两个函数用来通知订阅者,被观察的对象将停止发送数据以
- 本文实例讲述了Android TextView中文字通过SpannableString设置属性的方法。分享给大家供大家参考,具体如下:在An
- 最近项目中需要实现定时执行任务,比如定时计算会员的积分、调用第三方接口等,由于项目采用spring框架,所以这里结合spring框架来介绍。
- 实现功能:模拟简单登录功能,登录成功跳转新页面,登录失败在原登录界面提示登录失败信息开发环境:eclipseTomcat-8.0预备知识:H
- 报错翻译: compileSdkVersion android-24”需要JDK 1.8或更高版本编译。报错现象如下图:原因:st