本文实例讲述了java堆排序原理与实现方法。分享给大家供大家参考，具体如下：
堆是一个数组，被看成一个近似完全二叉树。
举例说明：
堆的性质：
1.已知元素在数组中的序号为i
其父节点的序号为 i/2的整数
其左孩子节点的序号为2*i
其右孩子节点的序号为2*i+1
2.堆分为最大堆和最小堆
在最大堆中，要保证父节点的值大于等于其孩子节点的值
在最小堆中，要保证父节点的值小于等于其孩子节点的值
java实现堆排序
我要评论
public class myheapsort {
public void heap_sort(int[] a) {
/**
* 这个函数完成堆排序
* 先构建一个最大堆
* 将数组中第一个元素和最后一个交换，
* 堆的长度减一
* 在从第一个位置开始保证堆的性质调用max_heapify()函数。
* 这样保证目前最大的元素在数组的最后位置。
* 以此类推，直到最后一个元素。
*/
build_max_heap(a);
for (int i = a.length - 1; i >= 1; i--) {
int temp = a[0];
a[0] = a[i];
a[i] = temp;
max_heapify(a, 0, i);
}
}
public void build_max_heap(int[] a) {
/**
* 这个函数用来构建堆
* a:待排序的数组
* （for循环中i的值从数组长度的一般开始取，是因为完全二叉树的性质，
* 一半的节点叶根节点所以从叶节点开始向上遍历来保证堆的性质）
*/
for (int i = a.length/2; i >= 0; i--) {
max_heapify(a, i, a.length);
}
}
public void max_heapify(int[] a, int i, int heap_size) {
/**这个函数用来维护堆的性质，
* 保证以序号为i的元素为根节点的子树中，父节点的值大于其孩子节点的值。
* a:待排序数组
* i：在数组a中的序号
* heap_size:堆的大小
*/
int largest = i;
int l = i * 2 + 1;
int r = i * 2 + 2;
if (l < heap_size && a[l] > a[i]) largest = l;
if (r < heap_size && a[r] > a[largest]) largest = r;
if (largest != i) {
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
max_heapify(a, largest, heap_size);
}
}
public static void main(string[] args) throws exception {
system.out.println("移动技术网测试结果：");
int[] a = new int[]{1,3,2,5,34,23,44,15,67,45};
new myheapsort().heap_sort(a);
for (int x : a) system.out.println(x);
}
}
代码中例子的运行结果：
ps：这里再为大家推荐一款关于排序的演示工具供大家参考：
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
更多关于java算法相关内容感兴趣的读者可查看本站专题：《java数据结构与算法教程》、《java操作dom节点技巧总结》、《java文件与目录操作技巧汇总》和《java缓存操作技巧汇总》
希望本文所述对大家java程序设计有所帮助。
如对本文有疑问， 点击进行留言回复！！
集合框架——Map、泛型以及Collection算法常用方法
Elasticsearch 升级 7.x 版本后，我感觉掉坑里了
Mybatis的插件运行原理以及如何编写一个Mybatis的插件
网友评论