堆排序算法(Java实现)

 1 package sort;
 2 
 3 public class HeapSort {
 4     static void heapSort(int []a,int len){
 5         int i;
 6         for(i=len/2;i>=0;i--){ /*把a[]构造成一个大顶堆*/
 7             HeapAdjust(a,i,len);
 8         }
 9         for(i=len;i>0;i--){
10             swap(a,0,i); /*交换堆顶最大元素和堆尾最小元素*/
11             HeapAdjust(a,0,i-1);  /*把交换后的堆a[0,i-1]，再次构造成大顶顶，使堆顶元素为最大值*/
12         }
13     }
14     static void HeapAdjust(int []a,int start,int len){
15         int temp,j;
16         temp=a[start];
17         for(j=2*start;j<=len;j*=2){   /*从index最大的有孩子的节点开始筛选，堆排*/
18             if(j<len&&a[j]<a[j+1])    /*是index=j的元素为较大的元素*/
19                 j++;
20             if(temp>=a[j])
21                 break;
22             a[start]=a[j];            /*将较大元素赋值给父节点*/
23             start=j;
24         }
25         a[start]=temp;              
26     }
27     static void swap(int a[],int low,int high){
28         int temp=a[low];
29         a[low]=a[high];
30         a[high]=temp;
31     }
32     public static void main(String []args){
33         int[] b = { 49, 38, 65, 97, 76, 13, 27, 50 };
34         heapSort(b, b.length - 1);
35         for(int w:b)
36             System.out.print(" "+w);
37     }
38 }