java堆排序概念原理介绍
作者:laozhang 时间:2021-08-30 12:31:58
堆排序介绍:
堆排序可以分为两个阶段。在堆的构造阶段,我们将原始数组重新组织安排进一个堆中;然后在下沉排序阶段,我们从堆中按顺序取出所有元素并得到排序结果。
1.堆的构造,一个有效的方法是从右到左使用sink()下沉函数构造子堆。数组的每个位置都有一个子堆的根节点,sink()对于这些子堆也适用,如果一个节点的两个子节点都已经是堆了,那么在该节点上调用sink()方法可以把他们合并成一个堆。我们可以跳过大小为1的子堆,因为大小为1的不需要sink()也就是下沉操作,有关下沉和上浮操作可以参考我写的优先队列那篇。
2.堆的排序,我们通过第一步操作构造了一个堆,在这个堆中,根节点永远是最大值的节点,所以我们把根节点的值与数组最后的值进行交换,在使用sink()下沉来维护堆的结构即可。
具体代码实现:
public class PQSort{
public static void main(String[] args){
int[] a = {9,1,7,5,3,9,12,56,21,45};
sort(a);
for(int i=0;i<a.length;i++) {
System.out.print(a[i]+" ");
}
}
//排序方法
public static void sort(int[] a){
int N = a.length-1;
//通过下沉操作构造堆,因为下标从0开始,所以子节点为2*k+1和2*k+2;
for(int k = (N-2)/2;k>=0;k--){
sink(a,k,N);
}
//通过不断把堆中最大值放到数组的后面来排序
while(N>0){
exch(a,0,N--);
sink(a,0,N);
}
}
//下沉函数
private static void sink(int[] a, int i, int n){
while(2*i+1<=n){
int j = 2*i+1;
if(j<n&&a[j]<a[j+1]) j++;
if(a[i]>a[j]) break;
exch(a,i,j);
i=j;
}
}
//交换函数
private static void exch(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
运行结果:
标签:java,堆排序
0
投稿
猜你喜欢
Java数据结构之顺序表的实现
2023-06-22 00:47:26
Spring注解@Configuration与@Bean注册组件的使用详解
2022-09-13 01:52:56
JDK14之jpackage打包命令的使用
2022-09-29 19:57:19
Spring bean的实例化和IOC依赖注入详解
2023-11-23 23:57:15
IP查询系统的异步回调案例
2023-11-10 18:22:24
实例详解SpringBoot默认的JSON解析方案
2023-07-21 07:34:20
eclipse如何搭建Springboot项目详解
2023-11-29 04:52:36
解读List list=new ArrayList()是怎么回事
2022-04-17 12:28:22
一篇文章带你Java Spring开发入门
2021-06-25 10:04:15
Springboot如何使用mybatis实现拦截SQL分页
2021-08-15 13:16:56
java多线程复制文件的实例代码
2022-03-04 04:29:54
详解Mybatis极其(最)简(好)单(用)的一个分页插件
2021-09-25 03:00:35
Java如何使用Query动态拼接SQL详解
2022-12-31 09:40:14
IDEA 2020.3最新永久激活码(免费激活到 2099 年,亲测有效)
2023-07-14 05:37:43
Java中的泛型方法详解及简单实例
2023-09-11 13:28:05
SpringBoot自动配置原理分析
2022-03-02 17:42:51
JAVA实现对阿里云DNS的解析管理
2023-11-24 13:25:15
详解java 三种调用机制(同步、回调、异步)
2023-11-25 07:59:57
SpringBoot基于Swagger2构建API文档过程解析
2022-12-06 20:42:58
Java基础之Thymeleaf的简单使用
2023-08-24 19:00:22