堆排序代码实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了堆排序代码实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1696字,纯文字阅读大概需要3分钟。
内容图文
![堆排序代码实现](/upload/InfoBanner/zyjiaocheng/1029/1edd2a2efa5242ccaaab02f981c2941c.jpg)
package com.atguigu.tree;
import java.util.Arrays;
/**
* @创建人 wdl
* @创建时间 2021/3/26
* @描述
*/
public class HeapSort {
public static void main(String[] args) {
//要求将数组进行升序排序
int arr[]={4,6,8,5,9};
heapSort(arr);
}
//编写一个堆排序的方法
public static void heapSort(int arr[]){
int temp=0;
System.out.println("堆排序");
// //分步完成
// adjustHeap(arr,1,arr.length);
// System.out.println("第一次"+ Arrays.toString(arr));//4,9,8,5,6
// adjustHeap(arr,0,arr.length);
// System.out.println("第二次"+Arrays.toString(arr));//9,6,8,5,4
//完成我们最终代码
//将无序序列构建成一个堆,根据升序需求求选择大顶堆或小顶堆
for (int i=arr.length/2-1;i>=0;i--){
adjustHeap(arr,i,arr.length);
}
for(int j=arr.length-1;j>0;j--){
//交换
temp=arr[j];
arr[j]=arr[0];
arr[0]=temp;
adjustHeap(arr,0,j);
}
System.out.println(Arrays.toString(arr));//9,6,8,5,4
}
/**
*功能:完成将以i对应的非叶子节点的树调整成大顶堆
* 举例int arr[]={4,6,8,5,9};=>i=1=>adjustHeap=>得到4,9,8,5,6
* 如果我们再次调用adjustHeap传入的是i=0=>得到9,6,8,5,4
*
* @param arr 待调整的数组
* @param i 表示非叶子节点在数组中索引
* @param length 表示对多少个元素继续进行调整,length是在逐渐的减少
*/
//将一个数组(二叉树),调整成一个大顶堆
public static void adjustHeap(int arr[],int i,int length){
int temp=arr[i];//先取出当前元素的值,保存在临时变量
//开始调整
//1.k=i*2+1 k是i节点的左子节点
for(int k=i*2+1;k<length;k=k*2+1){
if(k+1<length&&arr[k]<arr[k+1]){//说明左子节点的值小于右子节点的值
k++;//k就指向右子节点
}
if(arr[k]>temp){//如果子节点大于父节点
arr[i]=arr[k];//把较大的值赋给当前节点
i=k;//!!!i指向k,继续循环比较
}else{
break;//!
}
}
//当for循环结束后,我们已经将以i为父节点的树的最大值,放在了最顶(局部)
arr[i]=temp;//将temp值放到调整后的位置
}
}
内容总结
以上是互联网集市为您收集整理的堆排序代码实现全部内容,希望文章能够帮你解决堆排序代码实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。