Java-堆排序
2024-09-04 18:39:01
public class Main { public static void main(String[] args) {
int a[] = {8, 2, 5, 6, 4, 8, 9, 7, 14, 2, 3, 6, 4};
a = heapSort(a);
for (int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println();
} //构建大根堆
private static int[] buildMaxHeap(int[] a) {
//从最后一个节点a.length-1的父节点(array.length-1-1)/2开始,直到根节点0,反复调整堆
int half = (a.length - 2) / 2;
for (int i = half; i >= 0; i--) {
adjustDownToUp(a, i, a.length);
}
return a;
} //将元素array[k]自下往上逐步调整树形结构
private static void adjustDownToUp(int[] a, int k, int length) {
int temp = a[k];
for (int i = 2 * k + 1; i < length - 1; i = 2 * i + 1) { //i为初始化为节点k的左孩子,沿节点较大的子节点向下调整
if (i < length && a[i] < a[i + 1]) { //取节点较大的子节点的下标
i++; //如果节点的右孩子>左孩子,则取右孩子节点的下标
}
if (temp >= a[i]) { //根节点 >=左右子女中关键字较大者,调整结束
break;
} else { //根节点 <左右子女中关键字较大者
a[k] = a[i]; //将左右子结点中较大值array[i]调整到双亲节点上
k = i; //修改k值,以便继续向下调整
}
}
a[k] = temp; //被调整的结点的值放入最终位置
}
//堆排序
public static int[] heapSort(int[] array) {
array = buildMaxHeap(array); //初始建堆,array[0]为第一趟值最大的元素
for (int i = array.length - 1; i > 1; i--) {
swap(array, 0, i);//将堆顶元素和堆低元素交换,即得到当前最大元素正确的排序位置
adjustDownToUp(array, 0, i); //整理,将剩余的元素整理成堆
}
return array;
} //交换
public static void swap(int a[], int i, int j) {
a[i] = a[i] + a[j];
a[j] = a[i] - a[j];
a[i] = a[i] - a[j];
}
}
直接上代码,从代码中细细品味,分析。
思路:1、构建大堆或小堆 2、交换、调整
最新文章
- 从浏览器的console获取angularjs的scope
- linux shell ls -1 列显示文件
- iOS:关于获取网络类型和运营商信息
- poj 3592 Instantaneous Transference 缩点+最长路
- 道可道,非常道——详解promise
- python文本读写数据
- jqgrid again
- 关于antd 日期组件只选择年份,设置mode=year无法获取value的解决办法
- topcoder srm 465 div1
- 深入浅出javascript(六)对象
- (asp)JScript读写、复制、移动文件 asp也就那回事(4)
- TensorFlow笔记-02-Windows下搭建TensorFlow环境(win版非虚拟机)
- mysql改数据库名称
- 杭电OJ第11页2000-2009道题(C语言)
- RTMP、RTSP、HTTP视频协议详解(附:直播流地址、播放软件)
- Mysql字符串中有数字的排序问题
- Unreal开发HTC Vive程序,开启VR编辑模式
- pxe自动安装
- How to push master to QA branch in GIT
- [零基础学JAVA]Java SE基础部分-03.标识符、数据类型,数组,方法