Javascript 힙 정렬 알고리즘에 대한 자세한 설명

이 글은 주로 Javascript 힙 정렬 알고리즘과 그 예제를 소개합니다. 도움이 필요한 친구들이 참고할 수 있습니다.

힙 정렬은 두 가지 프로세스로 나뉩니다.

1.

힙은 본질적으로 다음을 충족해야 하는 완전한 이진 트리입니다. 트리에 있는 리프가 아닌 노드의 키워드는 왼쪽 및 오른쪽 하위 노드의 키워드보다 크거나 작지 않습니다( 존재하는 경우).

힙은 큰 루트 힙과 작은 루트 힙으로 구분됩니다. 큰 루트 힙은 오름차순 정렬에 사용되고 작은 루트 힙은 내림차순 정렬에 사용됩니다.

큰 루트 힙인 경우 조정 기능을 통해 값이 가장 큰 노드를 힙의 루트로 조정합니다.

2. tail에 힙 루트를 저장하고 나머지 시퀀스에 대해 조정 함수를 호출합니다. 조정이 완료된 후 tail에 최대 힙을 -1(-1, -2,...)에 저장합니다. , -i) , 나머지 순서를 조정하고 정렬이 완료될 때까지 이 과정을 반복합니다.

//调整函数
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(&#39;before: &#39; + elements);
sort(elements);
console.log(&#39; after: &#39; + elements);

효율성:

시간 복잡도: 최고: O(nlog2n), 최악: O(nlog2n), 평균: O(nlog2n).

공간 복잡도: O(1).

안정성: 불안정

위 내용은 이 장의 전체 내용입니다. 더 많은 관련 튜토리얼을 보려면 JavaScript 비디오 튜토리얼을 방문하세요.