Javascript堆排序算法详解
堆排序分为两个过程:
1.建堆。
堆实质上是完全二叉树,必须满足:树中任一非叶子结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
堆分为:大根堆和小根堆,升序排序采用大根堆,降序排序采用小根堆。
如果是大根堆,则通过调整函数将值最大的节点调整至堆根。
2.将堆根保存于尾部,并对剩余序列调用调整函数,调整完成后,再将最大跟保存于尾部-1(-1,-2,...,-i),再对剩余序列进行调整,反复进行该过程,直至排序完成。
//调整函数 functionheadAdjust(elements,pos,len){ //将当前节点值进行保存 varswap=elements[pos]; //定位到当前节点的左边的子节点 varchild=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; } } //构建堆 functionbuildHeap(elements){ //从最后一个拥有子节点的节点开始,将该节点连同其子节点进行比较, //将最大的数交换与该节点,交换后,再依次向前节点进行相同交换处理, //直至构建出大顶堆(升序为大顶,降序为小顶) for(vari=elements.length/2;i>=0;i--){ headAdjust(elements,i,elements.length); } } functionsort(elements){ //构建堆 buildHeap(elements); //从数列的尾部开始进行调整 for(vari=elements.length-1;i>0;i--){ //堆顶永远是最大元素,故,将堆顶和尾部元素交换,将 //最大元素保存于尾部,并且不参与后面的调整 varswap=elements[i]; elements[i]=elements[0]; elements[0]=swap; //进行调整,将最大)元素调整至堆顶 headAdjust(elements,0,i); } } varelements=[3,1,5,7,2,4,9,6,10,8]; console.log('before:'+elements); sort(elements); console.log('after:'+elements);
效率:
时间复杂度:最好:O(nlog2n),最坏:O(nlog2n),平均:O(nlog2n)。
空间复杂度:O(1)。
稳定性:不稳定