x-note
Search…
Introduction
FE
正则表达式
Git
基础算法
冒泡排序
插入排序
选择排序
快速排序
归并排序
希尔排序
堆排序
桶排序
计数排序
基数排序
二叉树的遍历
HTTP
Protocol Buffers
gRPC
设计模式
Powered By GitBook
堆排序
堆排序（Heapsort）就是把最大（小）堆的最大（小）数取出，然后继续将剩余的元素重新构建最大（小）堆，直到剩余数只有一个时结束。
最大堆：最大堆中的最大元素值出现在根结点（堆顶），堆中每个父节点的元素值都大于等于其孩子结点（如果存在） 最小堆：最小堆中的最小元素值出现在根结点（堆顶），堆中每个父节点的元素值都小于等于其孩子结点（如果存在）
  • 平均时间复杂度：
    O(nlog⁡2n)\mathcal{O}({n}\log_{2}{n})
    ​
  • 最好时间复杂度：
    O(nlog⁡2n)\mathcal{O}({n}\log_{2}{n})
    ​
  • 最坏时间复杂度：
    O(nlog⁡2n)\mathcal{O}({n}\log_{2}{n})
    ​
  • 空间复杂度：
    O(1)\mathcal{O}(1)
    ，最大为
    O(n)\mathcal{O}(n)
    ​
  • 稳定性：不稳定
  • 排序方式：原地（in-place）
堆（二叉堆）是一种近似于完全二叉树的结构，这使得堆可以利用数组来表示。
Could not load image
仔细观察能够轻易地出父节点与其孩子节点的下标之间的关系：
  • 节点 i 的父节点坐标：
    Parent(i)=floor(i−12)Parent(i) = floor(\dfrac{i - 1}{2})
  • 节点 i 的左节点坐标：
    Left(i)=2i+1Left(i) = 2i + 1
  • 节点 i 的右节点坐标：
    Right(i)=2(i+1)Right(i) = 2(i + 1)
完全二叉树，在不考虑二叉树最后一层的情况下，其余层的节点都是满的。也就是说，具有 n 个节点的完全二叉树的深度为
k=log2n+1k = log_{2}n + 1
，深度为 k 的完全二叉树至少有
2k{2}^{k}
 个节点，至多有
2k+1{2}^{k + 1}
 个节点。
一般实现：
/*
* 数组元素交换函数
*/
function swap(arr, i, j){
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
​
function heapSort(arr) {
buildMaxHeap(arr);
for (let i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
maxHeapify(arr, 0, i);
}
​
/**
* 构建最大堆
**/
function buildMaxHeap(arr) {
const heapSize = arr.length;
let iParent = (heapSize - 1) >> 1; // Math.floor((heapSize - 1) / 2);
for (let i = iParent; i >= 0; --i) {
maxHeapify(arr, i, heapSize);
}
}
​
/**
* 从 index 开始检查并保持最大堆性质
**/
function maxHeapify(arr, index, heapSize) {
let iMax = index,
iLeft = 2 * index + 1,
iRight = 2 * (index + 1);
if (iLeft < heapSize && arr[index] < arr[iLeft]) {
iMax = iLeft;
}
if (iRight < heapSize && arr[iMax] < arr[iRight]) {
iMax = iRight;
}
if (iMax != index) {
swap(arr, iMax, index);
maxHeapify(arr, iMax, heapSize); // 递归调整
}
}
return arr;
}
Previous
希尔排序
Next
桶排序
Last modified 3yr ago
Copy link