《排序算法》——堆排序(大顶堆,小顶堆,Java)

简介: 十大算法之堆排序:堆的定义如下:   n个元素的序列{k0,k1,...,ki,…,k(n-1)}当且仅当满足下关系时,称之为堆。   " ki=k2i+1.(i=1,2,…,[n/2])"   若将和此次序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树,   则完全二叉树中每一个节点的值的都大于或等于任意一个字节的值(如果有的话),称之为大顶堆。
十大算法之堆排序:

堆的定义如下:
  n个元素的序列{k0,k1,...,ki,…,k(n-1)}当且仅当满足下关系时,称之为堆。
  " ki<=k2i,ki<=k2i+1;或ki>=k2i,ki>=k2i+1.(i=1,2,…,[n/2])"

  若将和此次序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树,

  则完全二叉树中每一个节点的值的都大于或等于任意一个字节的值(如果有的话),称之为大顶堆。

  则完全二叉树中每一个节点的值的都小于或等于任意一个字节的值(如果有的话),称之为小顶堆。

  由此,若序列{k0,k1,…,k(n-1)}是堆,则堆顶元素(或完全二叉树的根)必为序列中n个元素的最小值(或最大值)。

  倘若给堆中每一个节点都赋予一个整数值标签,根节点被标记为0,对于每一个标记为i的节点,其左子节点(若存在的话)被标记为2*i+1,其右子节点(若存在的话)被标记为2*i+2,对于一个标记为i的非根节点,其父节点被标记为(i-1)/2。使用这个标记,我们能够将堆存储在数组中,节点存储在数据中的位置就使其标签。


package sort;

import java.util.Arrays;

/*
 * 堆排序
 * 堆的定义:满足 Ki <= K2i+1 Ki<=K2i+2 为小顶堆,满足 Ki >= K2i+1 Ki>=K2i+2 为大顶堆
 * 此为大顶堆的代码实例,小顶堆类似
 */
public class duiSort {

	static int[] arr  = {
		16,7,3,20,17,8                   //定义待排序数组
	}; 
	public static void main(String[] args) {
		
		buildHeap();//建立大顶堆并排序
		System.out.println("排序好的为:" + Arrays.toString(arr));
	}
	
	private static void buildHeap() {
		// TODO Auto-generated method stub
		int len = arr.length;
		for(int i =len/2 -1 ;i>=0;i--)            //建立大顶堆
		{
			sortHeap(i,len);
		}
		System.out.println("建立好的大顶堆如下:" + Arrays.toString(arr));
		for(int j = len-1; j >0; j --)        //对大顶堆进行排序
		{
			swap(0,j);
			sortHeap(0,j);
		}
	}

	private static void sortHeap(int i, int len) {
		// TODO Auto-generated method stub
		int left = 2*i+1;         //定义左节点
		int right = 2*i +2;     //定义右节点
		int large = 0;         //存放三个节点中最大节点的下标
		if(len >left && arr[left] > arr[i])    //如果左孩子大于根节点 将左孩子下标赋值给large
			large = left; 
		else                                                   //否之,将根节点下标赋值给large
			large = i;
		
		if(len > right && arr[right] > arr[large])
			large = right;                                //若右孩子节点大于根节点,把右孩子节点下标赋值给large
		
		if(large != i)                  //若最大节点的下标不等于根节点的下标时,交换其值
		{
			swap(large,i);
			sortHeap(large,len);
		}
	}
	//交换对应下标值
	private static void swap(int m, int n) {
		// TODO Auto-generated method stub
		int temp ;
		temp = arr[m];
		arr[m] = arr[n];
		arr[n] = temp;
	}
}


相关文章
|
2月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
90 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
12天前
|
存储 算法 Java
Java 内存管理与优化:掌控堆与栈,雕琢高效代码
Java内存管理与优化是提升程序性能的关键。掌握堆与栈的运作机制,学习如何有效管理内存资源,雕琢出更加高效的代码,是每个Java开发者必备的技能。
41 5
|
1月前
|
安全 Java 编译器
Java对象一定分配在堆上吗?
本文探讨了Java对象的内存分配问题,重点介绍了JVM的逃逸分析技术及其优化策略。逃逸分析能判断对象是否会在作用域外被访问,从而决定对象是否需要分配到堆上。文章详细讲解了栈上分配、标量替换和同步消除三种优化策略,并通过示例代码说明了这些技术的应用场景。
Java对象一定分配在堆上吗?
|
2月前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
73 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
2月前
|
存储 算法 Java
🏗️Java零基础:深入了解Java 堆
【10月更文挑战第2天】本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
27 3
|
2月前
|
算法 搜索推荐 Java
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
这篇文章介绍了如何使用Java后端技术,结合Graphics2D和Echarts等工具,生成包含个性化信息和图表的海报,并提供了详细的代码实现和GitHub项目链接。
134 0
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
|
2月前
|
算法 搜索推荐
数据结构与算法学习十八:堆排序
这篇文章介绍了堆排序是一种通过构建堆数据结构来实现的高效排序算法,具有平均和最坏时间复杂度为O(nlogn)的特点。
75 0
数据结构与算法学习十八:堆排序
|
2月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
85 2
|
2月前
|
算法 搜索推荐
算法之堆排序
本文介绍了堆排序算法的原理和实现,通过构建最大堆或最小堆,利用堆的性质进行高效的排序,并提供了具体的编程实现细节和示例。
24 0
算法之堆排序
|
2月前
|
算法 Java Go
深入了解堆排序算法
深入了解堆排序算法
29 1