扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
java中堆排序的原理是什么？相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。
堆排序介绍：
堆排序可以分为两个阶段。在堆的构造阶段，我们将原始数组重新组织安排进一个堆中；然后在下沉排序阶段，我们从堆中按顺序取出所有元素并得到排序结果。
1.堆的构造，一个有效的方法是从右到左使用sink()下沉函数构造子堆。数组的每个位置都有一个子堆的根节点，sink()对于这些子堆也适用，如果一个节点的两个子节点都已经是堆了，那么在该节点上调用sink()方法可以把他们合并成一个堆。我们可以跳过大小为1的子堆，因为大小为1的不需要sink()也就是下沉操作，有关下沉和上浮操作可以参考我写的优先队列那篇。
2.堆的排序，我们通过第一步操作构造了一个堆，在这个堆中，根节点永远是大值的节点，所以我们把根节点的值与数组最后的值进行交换，在使用sink()下沉来维护堆的结构即可。
具体代码实现:
public class PQSort{
public static void main(String[] args){
int[] a = {9,1,7,5,3,9,12,56,21,45};
sort(a);
for(int i=0;i=0;k--){
sink(a,k,N);
}
//通过不断把堆中大值放到数组的后面来排序
while(N>0){
exch(a,0,N--);
sink(a,0,N);
}
}
//下沉函数
private static void sink(int[] a, int i, int n){
while(2*i+1<=n){
int j = 2*i+1;
if(ja[j]) break;
exch(a,i,j);
i=j;
}
}
//交换函数
private static void exch(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
} 运行结果:
看完上述内容，你们掌握java中堆排序的原理是什么的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注创新互联行业资讯频道，感谢各位的阅读！
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网