堆排序(js)

堆排序原理解释:

• 先将数组看成一个堆,最大的非叶子节点:(size/2),i节点的父亲节点:(i/2-1),i节点的左孩子节点:(i2+1),右孩子节点:(i2+2)
• 从最后一个非叶子节点开始将堆进行小顶堆排序
• 每次拿出根节点,并和最后一个节点进行交换
• 重新进行堆的建立
• 由此得到了有序数列,O(nlog₂n)
• 不适合少量数据,属于不稳定排序

code:

 //堆排序
 //let array = [24,1,6,45,23,11,2,34,8,54,14];
 let nodeHeapSort = (i,arrayLength)=>{
   //对节点i进行小顶堆排序
   let leftChild = i*2+1;
   let rightChild = i*2+2;
   let change;
   if(leftChild<arrayLength&&array[leftChild]<array[i]){
     change = array[leftChild];
     array[leftChild] = array[i];
     array[i] = change;
   }
   if(rightChild<arrayLength&&array[rightChild]<array[i]){
     change = array[rightChild];
     array[rightChild] = array[i];
     array[i] = change;
   }
 }
 let HeapSort = (length)=>{
 //对所有的非叶子节点进行排序
   for (let i=length;i>=0;i--){
     nodeHeapSort(i,length*2+1);
   }
 }
 //提取元素
 for(let j=array.length;j>0;j--){
   HeapSort(Math.floor((j-1)/2));
   let change = array[0];
   array[0] = array[j-1];
   array[j-1] = change;
 }
 console.log([...array]);