疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

java堆排序


 

   

  堆排序中的重点是对二叉堆这样一种数据结构的理解,二叉堆具有以下性质:

  任意节点小于它的后裔(小根堆),或者任意节点大于它的后裔(大根堆)。

  堆总是一颗完全树

  本文中的实现使用了大根堆这样的结构,类似于33,22,11,19,15,8,3这样的一组数据是满足大根堆性质的数据

  之后再来看大根堆这样的数据结构支持的一个很关键的操作,下沉:

  下沉操作能够实现堆结构的由上至下的有序化。下沉这个操作是作用于有子节点的父节点,类似于公司中上级不再能够胜任管理其下属的工作,则其应当在组织中一步一步下沉,直到找到其能胜任的位置。

  将22,33,31这样的结构转换为33,22,31这样的结构,就是下沉操作。

  我们为什需要下沉操作呢?

  两个作用,

  第一个是通过循环所有的非叶子节点,能够使得整个数组变为大根堆的结构

  第二个是在将根节点(当前最大元素)与无序区的末尾元素交换之后,需要重新对根节点进行下沉操作,使得无序区重新回到大根堆的结构

  堆排序的过程部分类似于选择排序,两者相同的部分是都是先找到最大的元素,之后与无序区中最后一个元素交换;不同的地方是寻找最大元素的过程选择排序是通过逐一的比较,而堆排序是靠大根堆的特性,根节点是无序区中最大的元素。

  以下为实现代码:

  public class heap_sort {

  public static void main(String[] args) {

  // 首元素不参与排序

  int[] intarry={0,12,1,90,2,11,9,4,6,13,5,3,33};

  heapsort(intarry);

  for(int i:intarry){

  System.out.print(i);

  System.out.print(",");

  }

  }

  public static void heapsort(int[] intarry){

  int N = intarry.length-1;

  //通过下面的for循环构造大根堆

  for(int i=N/2;i>0;i--){

  sink(intarry,i,N);

  }

  for(int i:intarry){

  System.out.print(i);

  System.out.print(",");

  }

  System.out.println("--大根堆构造完成");

  //通过下面的循环对数组进行排序

  while(N>1){

  exch(intarry,1,N--);

  sink(intarry,1,N);

  }

  }

  /***

  * 实现乱序情况下某个根节点的下沉操作

  * 本方法能够使得以k为根节点的子树为大根堆结构

  *

  * intarry为整个数组

  * k为需要进行下沉的根节点

  * n为需要进行下沉判断的范围

  */

  public static void sink(int[] intarry,int k,int n){

  while(2*k<=n){

  int j = 2*k;

  // int bigger=intarry[j]>intarry[j+1] ? j:j+1;

  if(j

  if(intarry[k]>=intarry[j]) break;

  //交换元素

  int temp=intarry[k];

  intarry[k]=intarry[j];

  intarry[j]=temp;

  k=j;

  }

  }

  public static void exch(int[] intarry,int a,int b){

  int temp=intarry[b];

  intarry[b]=intarry[a];

  intarry[a]=temp;

  }

  }