堆排序

 1 private static int[] heapSort(int[] arr) {
 2         if (arr==null||arr.length<2) {
 3             return arr;
 4         }
 5         for (int i = arr.length/2; i>=0; i--) {
 6             percDown(arr, i, arr.length);     // buildHeap;
 7         }
 8         for(int i=arr.length-1;i>0;i--){
 9             swap(arr, 0, i);
10             percDown(arr, 0, i);  //deleteMax;
11         }
12             return arr;
13     }
14     
15     private static void percDown(int[] arr,int index,int len) {
16         int child=0,tmp=0;
17         for (tmp=arr[index]; leftChild(index) < len; index=child) {
18             child=leftChild(index);
19             if(child!=len-1&&arr[child]<arr[child+1])
20                 child++;
21             if (tmp<arr[child]) 
22                 arr[index]=arr[child];
23         }
24         arr[index]=tmp;
25     }
26     
27     private static int leftChild(int i) {
28         return 2*i+1;
29     }
30     
31     private static void swap(int[] arr, int j, int i) {
32         int tmp=arr[j];
33         arr[j]=arr[i];
34         arr[i]=tmp;
35     }