堆排序

堆排序

堆的定义

  • 堆(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 条评论
登录 后参与评论

相关文章

来自专栏FD的专栏

Effective Testing with RSpec 3 (英文版)(序言)

Early praise for Effective Testing with RSpec 3

1734
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1112
来自专栏黑泽君的专栏

【填大坑】关于Struts2中的 No result defined for action and result input 错误

配置好了struts.xml,也写好了Action,可是提交表单后就报 No result defined for action and result inpu...

1134
来自专栏专知

2018年SCI期刊最新影响因子排行,最高244,人工智能TPAMI9.455

2018年6月26日,最新的SCI影响因子正式发布,涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹,其影响因子今年再创新高,达244.585...

1272
来自专栏linux驱动个人学习

高通msm8909耳机调试

1、DTS相应修改: DTS相关代码:kernel/arch/arm/boot/dts/qcom/msm8909-qrd-skuc.dtsi: 1 s...

7475
来自专栏码匠的流水账

java9系列(五)Stack-Walking API

java9新增这个类的目的是提供一个标准API用于访问当前线程栈,之前只有Throwable::getStackTrace、Thread::getStackTr...

421
来自专栏Ryan Miao

ehcache报错

jfinal2.0+tomcat7+ehcache2.6.11+Linux Linux version 2.6.18-164.el5 (mockbuild@x8...

3729
来自专栏跟着阿笨一起玩NET

c# 使用timer定时器操作,上次定时到了以后,下次还未执行完怎么处理

------解决方案-------------------------------------------------------- 开始的时候,禁用定时器,你...

2631
来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

5896
来自专栏CodingToDie

Awesome 项目

3395

扫码关注云+社区