並べ替えを選択する---積み上げアルゴリズム(Javascript版)

積み上げ順序は二つのプロセスに分けられます.
1.ヒープを作る
ヒープは実質的に完全な二叉樹であり、必ず満足しなければならない.樹の中のいずれかの非葉っぱの結点のキーワードは、その左右の子供(存在すれば)結点のキーワードよりも大きくない.
積み上げるのは:大きい根のヒープと小さい根のヒープ、昇順は並べ替えて大きい根のヒープを採用して、降順は並べ替えて小根のヒープを採用します.
大きなルートヒープであれば、最大値のノードは調整関数によってルートに調整される.
2.スタックの根を末尾に保存し、残りのシーケンスに調整関数を呼び出し、調整が完了したら、一番大きなかかとを末尾-1(-1、-2、...、-i)に保存し、残りのシーケンスを調整して、順序付けが完了するまで繰り返します.
 
以下のコードはnodejsで実行します.

//    
function headAdjust(elements, pos, len){

  //          

  var swap = elements[pos];



  //              

  var child = pos * 2 + 1;



  //  ，         

  while(child < len){

    //             ，           ，      

    //         

    if(child + 1 < len && elements[child] < elements[child + 1]){

      child += 1;

    }



    //             ，        ，          

    //     

    if(elements[pos] < elements[child]){

      elements[pos] = elements[child];

      pos = child;

      child = pos * 2 + 1;

    }

    else{

      break;

    }



    elements[pos] = swap;

  }

}


//   

function buildHeap(elements){

  //               ，              ，

  //           ,   ，               ，

  //        （     ，     ）

  for(var i=elements.length/2; i>=0; i--){

    headAdjust(elements, i, elements.length);

  }

}



function sort(elements){

  //   

  buildHeap(elements);



  //            

  for(var i=elements.length-1; i>0; i--){

    //         ， ，          ， 

    //         ，          

    var swap = elements[i];

    elements[i] = elements[0];

    elements[0] = swap;



    //    ，   ）       

    headAdjust(elements, 0, i);

  }

}



var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];

console.log('before: ' + elements);

sort(elements);

console.log(' after: ' + elements);

 
効率:
時間複雑度:最も良い:O(nlog 2 n)、最悪:O(nlog 2 n)、平均:O(nlog 2 n).
空間複雑度:O(1).
安定性:不安定