欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java堆排序概念原理介绍

程序员文章站 2024-02-27 21:15:15
堆排序介绍: 堆排序可以分为两个阶段。在堆的构造阶段,我们将原始数组重新组织安排进一个堆中;然后在下沉排序阶段,我们从堆中按顺序取出所有元素并得到排序结果。 1...

堆排序介绍:

堆排序可以分为两个阶段。在堆的构造阶段,我们将原始数组重新组织安排进一个堆中;然后在下沉排序阶段,我们从堆中按顺序取出所有元素并得到排序结果。

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堆排序概念原理介绍