スタックソート(c++)

スタックは完全な二叉木と見なすことができ,大頂スタックと小頂スタックに分けられ,本稿では大頂スタックを例にスタック並べ替えを実現する.
(1)炉を建てる
まず、与えられたシーケンスを完全な二叉木に変換し、各ノードの値が2つのサブノードの値よりも大きくなるように徐々に調整するため、最初の非リーフノードから徐々に前方に調整する必要がある(リーフノードはサブノードよりも大きな状況が存在しないため、非リーフノードから前方に調整する).合計n要素があると仮定すると、では、最初に調整されたノードはn/2である.
(2)交換・調整
各調整後に第1の最大のノードと尾のノードをシフトするたびに、各ラウンドが最大で末尾にあり、その後、第1のノードを再スタックして大頂スタックになるように調整し、その後、再び交換して調整して往復する.

void shift(int a[], int low, int high){
    //      low            
    int temp = a[low];
    int i = low, j = 2*i; //i      ，j i    ，
    while(j <= high){
        // i          
        if(a[j] < a[j+1]) //          
            j++;
        if(a[j] > temp){ //                
            a[i] = a[j];
            i = j;
            j = 2 * i;
        }
        else
            break;
    }
    a[i] = temp;
}

void heapSort(int a[], int n){
    //     1  
    int i;
    int temp;
    for (i = n/2; i >= 1; --i) //  ，         n/2        
    {
        shift(a, i, n);
    }
    
    for (i = n; i >= 2; ++i)//           ，  n-1     ，   
    {
        tmep = a[1];//                  ，            
        a[1] = a[i];
        a[i] = temp;
        shift(a, 1, n-1);
    }
}