java中什么是堆排序?堆排序介绍

如果下载的源码需要作者授权,请更换源码。本站免费分享资源不会增加授权

本篇文章给大家带来的内容是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<a.length;i++) {    System.out.print(a[i]+" ");   }   }  //排序方法  public static void sort(int[] a){    int N = a.length-1;    //通过下沉操作构造堆,因为下标从0开始,所以子节点为2*k+1和2*k+2;    for(int k = (N-2)/2;k>=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(j<n&&a[j]<a[j+1]) j++;    if(a[i]>a[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中什么是堆排序?堆排序介绍

本文由(壳先生)整理自网络,如转载请注明出处:https://www.mrshell.com;
本站发布的内容若侵犯到您的权益,请邮件联系 i@mrshell.com 删除,我们将及时处理!
===========================================================================

1. 本站大部分下载资源收集于网络,不保证其完整性以及安全性,请下载后自行测试。
2. 本站资源仅供学习和交流使用,版权归资源原作者所有,请在下载后24小时之内自觉删除。
3. 不得使用于非法商业用途,商用请支持正版!不得违反国家法律,否则后果自负!
4. 若作商业用途,请购买正版,由于未及时购买和付费发生的侵权行为,与本站无关。
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!

=================================================================

壳先生 » java中什么是堆排序?堆排序介绍

发表评论

提供最优质的资源集合

立即查看 了解详情