Java 实现 堆排序

关键点 ：

• 平衡二叉树；
• 任意父节点都大于（小于）子节点；
• 用数组来储存。(父节点为arr[i]，则左节点arr[i<<1+1]，右节点arr[i<<1+2];)

思路：
1:构建最大顶堆；
2:取出最大顶的“顶”，调整堆；

public class ArrayHeap  {
    
    private void initHeap(int[] arr,int length) {
        if (arr==null||arr.length==0) {
            return;
        }
        int num = length/2-1;
         
        for( ;num>=0;num--){
            adjustHeap(arr, num, length);
        }
        
    }
    private void adjustHeap(int[] arr, int index,int length) {
        if (arr==null||arr.length==0||index<0||index>length||lastIndex<0||length>arr.length) {
            return;
        }
                int temp = arr[num];
        while (2*index+1<=length) {
            int left = index<<1+1;
            int right = left+1;
            int maxsonindex = right<=length?arr[left]>arr[right]?left:right:left;
            if (arr[index]<arr[maxsonindex]) {
                swap(arr[index], arr[maxsonindex]);
            }
            index+=index;
        }
        
    }
    private void swap(int a,int b) {
         a = a + b;
         b = a - b;
         a = a - b;
        
    }
    public void heapSort(int[] arr) {
        if (arr==null||arr.length==0) {
            return;
        }
        int length = arr.length;
        initHeap(arr,length);
        
        for(int i = 0;i<length-1;i++){
            swap(arr[0], arr[length-1-i]);
            adjustHeap(arr, 0, length--);
        }
        
    }
}