堆
要理解堆排序，首先要了解堆这个数据结构，因为堆排序是利用堆这种数据结构而设计的一种排序算法。堆首先是一种完全二叉树(满二叉树、完全二叉树、平衡二叉树、二叉排序树、红黑树or平衡二叉搜索树、哈弗曼树or最优二叉树)，其次满足下面的性质：
- 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆，即：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] ；
- 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆，即：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] 。
堆排序
堆排序是一种选择排序，最坏，最好，平均时间复杂度均近似为O(nlogn)，是不稳定排序。
算法流程主要包括2部分(以大顶堆为例)：
- 构建初始堆，比如造成一个大顶堆，那么整个序列的最大值就是堆顶的根节点；
- 交换堆顶元素和末尾元素，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。
下面贴上javascript代码：
function sort(arr) {
//1.构建大顶堆
for (var i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
//从第一个非叶子结点从下至上、从右至左调整结构
adjustHeap(arr, i, arr.length);
}
//2.调整堆结构 && 交换堆顶元素与末尾元素
for (var j = arr.length - 1; j > 0; j--) {
swap(arr, 0, j);//将堆顶元素与末尾元素进行交换
adjustHeap(arr, 0, j);//从第一个结点从下至上、从右至左调整结构
}
}
function adjustHeap(arr, i, length) {
var temp = arr[i];
for (var k = i * 2 + 1; k < length; k = k * 2 + 1) {//从i结点的左子结点开始，也就是2i+1处开始
if (k + 1 < length && arr[k] < arr[k + 1]) {//如果左子结点小于右子结点，k指向右子结点
k++;
}
if (arr[k] > temp) {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
arr[i] = arr[k];
i = k;
} else {
break;
}
}
arr[i] = temp;//将temp值放到最终的位置
}
function swap(arr, a, b) {
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
var arr = [22, 1, 324, 4, 6, 22, 11, 9, 8, 7, 6, 5, 4, 3, 2, 1];
sort(arr);
console.log(arr)//[ 1, 1, 2, 3, 4, 4, 5, 6, 6, 7, 8, 9, 11, 22, 22, 324 ]
小顶堆排序的话只需要改adjustHead函数中的两行代码：
-
if (k + 1 < length && arr[k] < arr[k + 1])改为if (k + 1 < length && arr[k] > arr[k + 1]) -
if (arr[k] > temp)改为if (arr[k] < temp)。
参考文献：
