堆排序

堆排序

堆的定义

  • 堆(heap),这里所说的堆是数据结构中的堆,而不是内存模型中的堆。堆通常是一个可以被看做一棵树,它满足下列性质:
  • [性质一] 堆中任意节点的值总是不大于(不小于)其子节点的值;
  • [性质二] 堆总是一棵完全树
  • 将任意节点不大于其子节点的堆叫做最小堆或小根堆,而将任意节点不小于其子节点的堆叫做最大堆或大根堆。常见的堆有二叉堆、左倾堆、斜堆、二项堆、斐波那契堆等等。

排序的过程

  1. 将数组建成最大堆或者最小堆
  2. 取出堆顶的数据和数组末尾的数据交换,此时对前面的数据再次建堆,再取堆顶的数据和数组中的倒数第二个交换,…………………….

代码实现

构造大顶堆

  • 实现从大到小的排序

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970

public class HeapSort { /** * 构造大顶堆 * 1. 根节点的值一定要比子节点的值大 * 堆的向下调整 * @param array 需要调整的数组 * @param start 调整的起始位置 * @param end 调整的终止位置 * 索引从0开始 * 当前节点的左节点: 2*i+1 * 右节点: 2**i+2 */ public static void max_heap_down(int[] array,int start,int end){ int currentIndex=start; //保存当前节点的下标 int leftIndex=2*currentIndex+1; //当前节点左节点的下标 //当当前节点的左节点的下标小于终止下标的时候,因为堆是一个完全的二叉树,因此只要没有左子树就一定没有右子树,因此只需要判断左节点的下标即可 //只要满足这个条件就表示一定存在左右节点 while(leftIndex<end){ //当左节点的值小于右节点,那么此时只需要将当前值和右节点的值比较,这里的leftIndex+1是右子节点的下标 //如果没有执行if体内的语句,那么此时的左右节点最大的下标就是左节点的下标 if(array[leftIndex]<array[leftIndex+1]){ leftIndex++; //此时的下标编程右节点的下标 } //如果当前节点大于等于左右子节点中的最大值,那么就不用调整了,直接跳出 if (array[currentIndex]>=array[leftIndex]) { break; }else { //如果小于,此时需要调整,将当前节点和左右子节点最大值交换 int temp=array[currentIndex]; //交换数字 array[currentIndex]=array[leftIndex]; array[leftIndex]=temp; currentIndex=leftIndex; //此时的当前节点的下标 leftIndex=2*currentIndex+1; //当前节点的左子节点也需要改变了 } } } /** * 堆排序,从小到大 * @param array 待排序的数组 */ public static void heap_sort_asc(int[] array){ //从索引为array.length/2-1的位置到0,开始向下调整,那么调整好的数组就是一个大顶堆 for(int i=array.length/2-1;i>=0;i--){ //进行向下调整 max_heap_down(array, i, array.length-1); } //从最后一个元素开始对序列进行调整,不断的调整,直到第一个元素 for (int i = array.length-1; i >0; i--) { //此时array[0]就是最大的元素,因此和最后一个元素交换 int temp=array[i]; array[i]=array[0]; array[0]=temp; //此时最后一个元素就是最大的,因此我们对前面的元素继续构造大顶堆 max_heap_down(array, 0, i-1); } } public static void main(String[] args) { int[] array={12,3,4,45,1,45,6,72,4}; heap_sort_asc(array); for (int i = 0; i < array.length; i++) { System.out.println(array[i]); } }}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏zhisheng

Java常用排序算法/程序员必须掌握的8大排序算法

Java常用排序算法/程序员必须掌握的8大排序算法 分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排...

4978
来自专栏专注研发

选择排序—堆排序(Heap Sort) 没看明白,不解释

时称之为堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)。 若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或...

872
来自专栏Golang语言社区

Golang语言社区--【基础知识】常量

常量是指该程序可能无法在其执行期间改变的固定值。这些固定值也被称为文字。 常量可以是任何像一个整型常量,一个浮点常量,字符常量或字符串文字的基本数据类型。还有枚...

3265
来自专栏ShaoYL

C语言基础-运算符

3386
来自专栏ACM算法日常

基础算法|6 折半插入排序 - HDU 1412

我们之前已经了解了5种基础算法,是否自己找了一些题练练手呢~话不多说,让我们进入第6中基础算法的学习吧。本篇我们将学习又一种排序算法——折半插入排序算...

1064
来自专栏我的技术专栏

数据结构图文解析之:直接插入排序及其优化(二分插入排序)解析及C++实现

1683
来自专栏Golang语言社区

Golang语言社区--【基础知识】常量

常量是指该程序可能无法在其执行期间改变的固定值。这些固定值也被称为文字。 常量可以是任何像一个整型常量,一个浮点常量,字符常量或字符串文字的基本数据类型。还有枚...

3617
来自专栏微信公众号:Java团长

十大经典排序算法最强总结(含Java代码实现)

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的位...

2551
来自专栏架构师小秘圈

秒懂排序算法

作者:郭耀华,来自:cnblogs.com/guoyaohua 0、排序算法说明 0.1 排序的定义 对一序列对象根据某个关键字进行排序。 0.2 术语说明 稳...

4095
来自专栏技术博文

PHP实现经典算法

前提:分别用冒泡排序法,快速排序法,选择排序法,插入排序法将下面数组中的值按照从小到大的顺序进行排序。 $arr = array(1,43,54,62,21,6...

2724

扫码关注云+社区

领取腾讯云代金券