-
堆排序原理解释:
- 先将数组看成一个堆,最大的非叶子节点:(size/2),i节点的父亲节点:(i/2-1),i节点的左孩子节点:(i2+1),右孩子节点:(i2+2)
- 从最后一个非叶子节点开始将堆进行小顶堆排序
- 每次拿出根节点,并和最后一个节点进行交换
- 重新进行堆的建立
- 由此得到了有序数列,O(nlog2n)
- 不适合少量数据,属于不稳定排序
-
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]);
堆排序(js)
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪：刷leetcod...
- 晚上儿子放学回来后，我一看儿子的衣服，很脏，手也不干净，我很生气，真想大声骂他，强忍了下去。 回家...
