掌握算法，先理解原理
堆排序算法.gif
堆排序（Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点.
最大堆的根节点是最大值
什么是堆
有序性、近似完全二叉树结构
建堆
function buildHeap(arr) {
len = arr.length;
for (var i = Math.floor(arr.length / 2);i>=0; i--) { //从堆的最后一个节点开始调整
adjustHeap(arr, i) //调整堆
}
}
从87节点开始调整，Math.floor(arr.lenfth / 2)
调整成最大堆
function adjustHeap(arr, i) {
var left = 2 * i + 1, // 左节点位置
right = 2 * i + 2, //右节点位置
largest = i; // 最大值位置
//如果左节点存在并且左节点大于 当前最大节点，交换位置
if (left < len && arr[left] > arr[largest]) {
largest = left
}
//如果右节点存在并且右节点大于 当前最大节点，交换位置
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
//如果发现修改了位置，则交换值，并且继续向上调整堆
if (largest !== i) {
swap(arr, i, largest);
adjustHeap(arr, largest)
}
}
交换位置 swap（）
function swap(arr, i, j) {
var temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
交换原理.jpg
堆排序算法
// 堆排序算法
function heapSort(arr) {
buildHeap(arr) //建堆
for (var i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i); //堆顶一定是最大元素，将堆顶和尾部元素交换，最大元素就保存在尾部，并且不参与后面的调整
len--; // 去掉这个是从大到小排序
adjustHeap(arr, 0) ///将最大的元素进行调整，将最大的元素调整到堆顶
}
return arr
}
前面是一步步拆分，接下来综合堆算法
// 建最大堆
var len; //定义成全局变量
function buildHeap(arr) {
len = arr.length;
for (var i = Math.floor(arr.length / 2);i>=0; i--) {
adjustHeap(arr, i) //调整堆
}
}
function adjustHeap(arr, i) {
var left = 2 * i + 1, // 左节点位置
right = 2 * i + 2, //右节点位置
largest = i; // 最大值位置
//如果左节点存在并且左节点大于 当前最大节点，交换位置
if (left < len && arr[left] > arr[largest]) {
largest = left
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
//如果发现修改了，则交换位置
if (largest !== i) {
swap(arr, i, largest);
adjustHeap(arr, largest)
}
}
//交换位置
function swap(arr, i, j) {
var temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
// 堆排序算法
function heapSort(arr) {
buildHeap(arr) //建堆
for (var i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i); //堆顶一定是最大元素，将堆顶和尾部元素交换，最大元素就保存在尾部，并且不参与后面的调整
len--; // 去掉这个是从大到小排序
adjustHeap(arr, 0) ///将最大的元素进行调整，将最大的元素调整到堆顶
}
return arr
}
var array = [11, 43, 24, 76, 89, 43, 65]
heapSort(array)
console.log(array) //打印结果 [ 11, 24, 43, 43, 65, 76, 89 ]
总结，看到这里，堆排序算法已经实现了，前面说什么来着，堆排序算法其实是的选择排序 的进一步优化，利用堆根节点是最大（小）值的特点，迅速找到最大（小）值，从而实现排序优化
