堆排序 2018-07-05

1.首先将无序序列（长度为n的数组）调整为堆，以大根堆为例
2.将堆顶元素和堆尾进行交换
3.将剩余的n-1个元素调整为堆，重复2,3.直至整个数组有序。

public void heapSort(int a[]){
        makeHeap(a,a.length);
        for(int i=a.length-1;i>=0;i--){
            swap(a,i,0);//将堆顶元素和末尾元素交换
            heapAdjust(a, 0, i);//重新对堆进行调整，注意当前位置是从0开始进行调整
        }
    }
    public void makeHeap(int a[],int n){
        for(int i=n/2-1;i>=0;i--){//从n/2-1位置开始调整
            heapAdjust(a,i,n);

        }
    }
    

    /**
     * @param a
     * @param i
     * @param j
     *<p>Description: </p>  
     */
    private void swap(int[] a, int i, int j) {
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
        
    }
    /**
     * @param a
     * @param i
     *<p>Description: 调整为大根堆，i为当前需要调整的节点</p>  
     */
    private void heapAdjust(int[] a, int i,int n) {
        int j=i*2+1;//i的左子节点
        while(j<n){
            if(j+1<n && a[j]<a[j+1]){//如果右子节点为大的，则j指向右边
                j++;
            }
            if(a[i]<a[j]){//j代表左右孩子中较大的那个
                swap(a, i, j);
            }
            else{//i所在的子树以满足大根堆的定义
                break;
            }
            i=j;//如果i,j交换后，j所在的子树可能不满足堆的定义，继续调整
            j=i*2+1;
        }
        
        
    }

    /**
     * @param args
     *<p>Description: </p>  
     */
    public static void main(String[] args) {

        //int a[]={16,7,3,20,17,8};
        int a[]={10,7,8,5,4,6,1};
        HeapSort h=new HeapSort();
        h.heapSort(a);
        System.out.println(Arrays.toString(a));
    }