JavaScriptクラシックソートアルゴリズム-スタックソート

スタックは、次の性質を持つ完全なツリーです.
各ノードの値は、その左右の子供のノードの値よりも大きいか、または等しい.
各ノードの値は、その左右の子供のノードの値以下であり、小さなトップスタックと呼ばれます.
次の図を示します.
同時に、スタック内のノードをレイヤ別に番号付けし、この論理構造を配列にマッピングすると、次のようになります.
この配列は論理的にスタック構造であり、簡単な式でスタックの定義を説明すると、
大頂炉:arr[i]>=arr[2 i+1]OR arr[i]>=arr[2 i]
小頂炉:arr[i]<=arr[2 i+1]OR arr[i]<=arr[2 i]

効率:

時間複雑度:O(nlog 2 n)
空間複雑度:O(1)

安定性あんていせい:不安定

JavaScriptコード実装：

function heapSort(array) {
    var temp;
    var i;
    var result = "";
    for (i = Math.floor(array.length / 2); i >= 0; i--) {
        heapAdjust(array, i, array.length - 1); //   array        
    }
    for (i = array.length - 1; i >= 0; i--) {
        /*        */
        temp = array[i];
        array[i] = array[0];
        array[0] = temp;
        /*             */
      heapAdjust(array, 0, i - 1);
        /*      */
        result += "
 " + (array.length - i).toString() + "       :";
        for (var n = 0; n < array.length; n++) {
            result += array[n] + ",";
        }
        /*        */
    }
    return result;
}
//      
//start       
//max       
function heapAdjust(array, start, max) {
    var temp, j;
    temp = array[start];//temp      
    for (j = 2 * start; j < max; j *= 2) {
        if (j < max && array[j] < array[j + 1]) {  //         
            ++j;
        }
        if (temp >= array[j])
            break;
            array[start] = array[j];
            start = j;
    }
    array[start] = temp;
}
 
var array = [50,45,40,20,25,35,30,10,15];
console.log(heapSort(array));    //10,15,20,25,30,35,40,45,50