文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java编程内功-数据结构与算法「堆排序」

2024-12-03 09:03

关注

一个数组中非叶子节点的个数 = arr.length / 2 - 1

代码案例

  1. package com.xie.tree; 
  2.  
  3. public class HeapSort { 
  4.     public static void main(String[] args) { 
  5.         int[] arr = new int[8000000]; 
  6.         for (int i = 0; i < 8000000; i++) { 
  7.             arr[i] = (int) (Math.random() * 800000000); 
  8.         } 
  9.         long start = System.currentTimeMillis(); 
  10.         heapSort(arr); 
  11.         long end = System.currentTimeMillis(); 
  12.         System.out.println("耗时:" + (end - start) + "ms"); 
  13.          
  14.     } 
  15.  
  16.     public static void heapSort(int[] arr) { 
  17.         int temp = 0; 
  18.         System.out.println("堆排序!!"); 
  19.  
  20.         //1.将无序序列构成一个堆,根据升序降序需求选择大顶堆或小顶堆 
  21.         for (int i = arr.length / 2 - 1; i >= 0; i--) { 
  22.             adjustHeap(arr, i, arr.length); 
  23.         } 
  24.         //2.将堆顶元素与数组末尾元素交换,将最大元素"沉"到数组末端 
  25.         //3.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。 
  26.         for (int j = arr.length - 1; j > 0; j--) { 
  27.             //交换 
  28.             temp = arr[j]; 
  29.             arr[j] = arr[0]; 
  30.             arr[0] = temp
  31.             adjustHeap(arr, 0, j); 
  32.         } 
  33.     } 
  34.  
  35.      
  36.     public static void adjustHeap(int[] arr, int i, int length) { 
  37.         //先取出当前元素的值,保存在临时变量 
  38.         int temp = arr[i]; 
  39.         //k = 2 * i + 1  是i节点的左子节点 
  40.         for (int k = 2 * i + 1; k < length; k = k * 2 + 1) { 
  41.             //当左子节点值小于右子节点值 
  42.             if (k + 1 < length && arr[k] < arr[k + 1]) { 
  43.                 k++;//k指向右子节点 
  44.             } 
  45.  
  46.             //如果子节点值大于父节点值 
  47.             if (arr[k] > temp) { 
  48.                 //把较大的值赋给当前节点 
  49.                 arr[i] = arr[k]; 
  50.                 //!!! i指向k 继续循环比较 
  51.                 i = k; 
  52.             } else { 
  53.                 break; 
  54.             } 
  55.         } 
  56.  
  57.         //当for循环结束后,我们已经将以 i 为父节点的树的最大值,放在了最顶。 
  58.  
  59.         //将temp值放到调整后的位置 
  60.         arr[i] = temp
  61.     } 

 【编辑推荐】

  1. 跟妹妹聊到 Java 16 新特征,真香!
  2. IT项目过多,管理太难?NO!因为你还没学会这七招
  3. 学了五年Python,这些网站让我相见恨晚,快来一起见识一下
  4. Java都到16了,为什么都还在用8,是越做越烂了么?
  5. 实在太神奇!Windows10这些黑科技小功能你都用过吗

 

来源:今日头条内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯