啊噢，又开始写算法学习的笔记了。最近在准备面试的过程中又把这些常见的排序算法拿出来复习复习，既然这篇写到了堆排序，那么就代表堆排序算法的概念被我忘的差不多了，写篇博客加深记忆吧。
在维基百科上看堆排序，上面有这么一张图，
[图片上传失败...(image-429679-1533643606451)]
可是原谅我概念真的忘的差不多了，所以理解不了这张图，于是我又找到另一个可视化的过程，一目了然，是别人放在github page上的一个页面，地址就在这里。所以本篇文章的堆排序的可视化动画，就参考这个吧。
堆排序（Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
通常堆是通过一维数组来实现的，在数组起始位置为0的情形中来看看堆节点的一些定义。
- 父节点i的左子节点在位置(2i + 1);
- 父节点i的右子节点在位置(2i + 2);
- 子节点i的父节点在floor((i - 1) / 2);
关于堆中节点的位置，有如上三个定义。
在堆的数据结构中，堆中的最大值总是位于根节点上。而堆中的一个很重要的操作就是最大堆调整(Max_Heapify)，即为将堆的末端子节点作调整，使得子节点永远小于父节点。
接下来看看这个关键的Max_Heapify最大堆调整的实现是怎样的：
maxHeapify(start, end) {
// 建立父节点指标和子节点指标
let dad = start;
let son = dad * 2 + 1;
// 若子节点指标超过范围，则直接跳出函数
if (son >= end)
return;
// 先比较两个子节点的大小 选择最大的
if (son + 1 < end && this.array[son] < this.array[son + 1])
son++;
// 如果父节点小于子节点，交换父子节点的内容再继续子节点与孙节点的比较
if (this.array[dad] < this.array[son]) {
this.swap(dad, son);
this.maxHeapify(son, end);
}
}
在进行最大堆调整的操作时，我们传入初始和终止的两个索引，并且根据我们刚提到的堆节点的定义，建立父节点和子节点指标。接下来如果子节点的指标超过的终止索引的范围，则直接跳出函数。否则的话我们比较两个子节点的大小，选择大的节点进行接下来的操作。
在两个节点中选取完较大节点后，我们比较父节点与子节点，如果父节点小于子节点，那么交换父子节点的内容，再递归的比较子节点与孙节点，直到调整完成。
完整的堆排序算法（javascript实现）如下：
/**
* 堆排序算法
*/
class HeapSort {
constructor(originalArray) {
// 拷贝数组，不修改原数组
this.array = [...originalArray];
}
swap(i, j) {
const temp = this.array[i];
this.array[i] = this.array[j];
this.array[j] = temp;
}
maxHeapify(start, end) {
// 建立父节点指标和子节点指标
let dad = start;
let son = dad * 2 + 1;
// 若子节点指标超过范围，则直接跳出函数
if (son >= end)
return;
// 先比较两个子节点的大小 选择最大的
if (son + 1 < end && this.array[son] < this.array[son + 1])
son++;
// 如果父节点小于子节点，交换父子节点的内容再继续子节点与孙节点的比较
if (this.array[dad] < this.array[son]) {
this.swap(dad, son);
this.maxHeapify(son, end);
}
}
sort() {
const len = this.array.length;
// 初始化 i从最后一个父节点开始调整
for (let i = Math.floor((len - 1) / 2); i >= 0; i--)
this.maxHeapify(i, len);
// 先将第一个元素和已排好的前一位做交换，再重新调整，直到排序完成
for (let i = len - 1; i > 0; i--) {
this.swap(0, i);
this.maxHeapify(0, i);
}
return this.array;
}
}
const array = [0, 9, 1, 8, 2, 7, 3, 6, 5, 4];
let heap = new HeapSort(array);
let res = heap.sort();
console.log(res);
sort函数里的两个for循环也要解释一下，第一个for循环，是堆的初始化，从最后一个父节点开始，调整整个数组的排序。而第二个for循环，是把第一个已经确定大小的元素和已经排好位的前一个元素做交换，再重新调整排序，直到整个排序完成。待for循环完成之后，整个数组也就呈从小到大的顺序了排好了。
理解完代码之后，再看看堆排序的时间复杂度，堆排序的平均时间复杂度，以及最优、最坏的时间复杂度都是O(nlog n)，而空间复杂度是O(1)，并且堆排序是一种不稳定排序。
文章中的源码在这里堆排序算法源码
我的博客即将搬运同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=1svchdt6unloa
网友评论