堆排序

父节点 r
左子节点2r+1
右子节点2r+2
叶节点数n/2

class Solution {
public:
    /**
     * @param A an integer array
     * @return void
     */
    void sortIntegers2(vector<int>& A) {
        // Write your code here
        /*
        vector<int>temp(A.size(),0);
        mergeSort(A,temp,0,A.size()-1);
        */
        //quickSort(A,0,A.size()-1);
        headSort(A);
    }
    
    
    void headSort(vector<int>& A){
        int n = A.size();
  //从最后一个不是叶节点的点开始调整
        for(int i = n/2-1;i>=0;i--) {
            headAdjust(A,i,n);
        }
        for(int i = n-1;i>0;i--){
            A[0] = A[i]^A[0];
            A[i] = A[i]^A[0];
            A[0] = A[i]^A[0];
            headAdjust(A,0,i);
        }
    }
    
//向下调整堆
    void headAdjust(vector<int>& A,int index,int length) {
        int i = index;
        int j = 2*index+1;
        while(j<length) {
            
            if(j+1<length&&A[j+1]>A[j]) {
                j++;
            }
            
           if(A[i]<A[j]) {
               A[i] = A[i]^A[j];
               A[j] = A[i]^A[j];
               A[i] = A[i]^A[j];
           } else {
               break;
           }
           i = j;
           j = 2*i+1;
        }
    }
}