堆排序

public int[]heapSort(int[] A, int n) {

            //循环建堆 

            for(int i=0;i

                buildMaxHeap(A,n-1-i); //建堆   n-1-i为最后一个元素的下标

                swap(A,0,n-1-i);   //交换堆顶和最后一个元素 

            } 

            return A;

         } 

         private void swap(int[] A, int i, intj) { 

            int tmp=A[i]; 

            A[i]=A[j]; 

            A[j]=tmp; 

         } 

         //对A数组从下标0到下标lastIndex建大顶堆 

         private void buildMaxHeap(int[] A, intlastIndex) { 

            //从lastIndex处节点（最后一个节点）的父节点开始 

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

                int k=i;  //k保存正在判断的节点 

                //如果当前k节点的子节点存在

                while(k*2+1<=lastIndex){ 

                     int biggerIndex=2*k+1;  //k节点的左子节点的索引为2K+1

                     //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在 

                     if(biggerIndex

                         //若果右子节点的值较大 

                        if(A[biggerIndex]

                             biggerIndex++;   //biggerIndex总是记录较大子节点的索引 

                         } 

                     } 

                    if(A[k]

                         swap(A,k,biggerIndex);  //交换他们 

         //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值 

                         k=biggerIndex; 

                     }else

                         break;   

}  //while 

}//for   

 }// buildMaxHeap方法