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);

   }

}