堆排序算法

啊噢,又开始写算法学习的笔记了。最近在准备面试的过程中又把这些常见的排序算法拿出来复习复习,既然这篇写到了堆排序,那么就代表堆排序算法的概念被我忘的差不多了,写篇博客加深记忆吧。

在维基百科上看堆排序,上面有这么一张图,

image

可是原谅我概念真的忘的差不多了,所以理解不了这张图,于是我又找到另一个可视化的过程,一目了然,是别人放在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),并且堆排序是一种不稳定排序。

文章中的源码在这里堆排序算法源码

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 215,384评论 6 497
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,845评论 3 391
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 161,148评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,640评论 1 290
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,731评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,712评论 1 294
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,703评论 3 415
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,473评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,915评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,227评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,384评论 1 345
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,063评论 5 340
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,706评论 3 324
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,302评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,531评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,321评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,248评论 2 352

推荐阅读更多精彩内容

  • 啊噢,又开始写算法学习的笔记了。最近在准备面试的过程中又把这些常见的排序算法拿出来复习复习,既然这篇写到了堆排序,...
    Originalee阅读 382评论 0 0
  • 版本记录 前言 将数据结构和算法比作计算机的基石毫不为过,追求程序的高效是每一个软件工程师的梦想。下面就是我对算法...
    刀客传奇阅读 3,903评论 0 0
  • 堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O...
    安然若知阅读 1,382评论 0 0
  • 能享福也能受罪,能人前也能人后,能站起来也能圪蹴得下,才活得坦然。 2016年4月29日,中国现代文坛的又一颗巨星...
    听海风吹的声音阅读 399评论 4 1
  • Quarter life crisis (四分之一人生危机)听起来挺扯淡的,今年却莫名其妙地感同身受了。二十岁的前...
    王湿人阅读 756评论 0 1