基础算法学习之(三):堆排序

mrli2016 发布于2019-08-20 11:34 / 2195人阅读

摘要：奇妙的记忆点不稳定内排序基本思想分为两步建堆与维持堆的性质首先我们要先理解堆是什么东西堆其实就是一个完全二叉树我们可以使用顺序表存储一个二叉树如下图所示来存储其中分为最大堆最小堆而最大堆就是上头大下头小最小堆则反之明白了堆的定义我们就可以开

奇妙的记忆点:

不稳定

内排序

基本思想:

分为两步,建堆与维持堆的性质,首先我们要先理解堆是什么东西.
堆其实就是一个完全二叉树,我们可以使用顺序表存储一个二叉树,如下图所示来存储:

其中分为最大堆最小堆,而最大堆就是上头大,下头小;最小堆则反之.
明白了堆的定义我们就可以开始学习堆排序了,堆排序其实也是分为有序区与无序区,其中无序区就是我们建好的最大堆,根节点就是堆中最大的数,我们逐个让最大元素进有序区并对堆结构进行调整,维持根节点最大的性质,直到堆中元素清空为止,就是堆排序的过程.

堆排序关键代码

//工具函数
function swapItem(pre,next,arr){
  var temp = arr[next];
  arr[next] = arr[pre];
  arr[pre] = temp;
}
function getLeft(i){
  return 2*i+1;
}
function getRight(i){
  return 2*i+2;
}

//维持堆的性质
function heapAdjust(arr,i,len){//数组,数组下标,堆元素长度(无序区长度)
  var large,l = getLeft(i),r = getRight(i);
  if(l < len&&arr[l] > arr[i]){
    large = l;
  }else{
    large = i;
  }
  if(r < len&&arr[r] > arr[large]){
    large = r;
  }
    //上述代码就是取节点也子节点三个元素之间的最大值
  if(large !== i){
    swapItem(large,i,arr);
    heapAdjust(arr,large,len);//防止堆性质被破坏,所以递归调用来维持堆性质
  }
}

//建堆
function heapBuild(arr,len){
  for(var i = Math.floor(len / 2) - 1;i>=0;i--){
    heapAdjust(arr,i,len);
  }
  //console.log(arr);
}

//堆排序本体如下
function heapSort(arr){
  var heapSize = arr.length;//堆(无序区)大小
  heapBuild(arr,heapSize);//建堆
  for(var i=heapSize-1;i>=1;i--){
    swapItem(0,i,arr);//堆顶部元素与堆底部元素交换(无序区->有序区)
    //console.log(arr);
    heapAdjust(arr,0,--heapSize);//维持堆性质(无序区)
  }
}
//测试代码
var arr=[91,60,96,13,35,65,46,65,10,30,20,31,77,81,22];
heapSort(arr);
console.log(arr);

记忆点:

最佳情况：T(n) = O(nlogn)

最差情况：T(n) = O(nlogn)

平均情况：T(n) = O(nlogn)

混合云 idc机房托管堆排序算法零基础学大数据算法学习之substr() 深度学习之概要

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/80649.html

算法学习之数据结构线性表、堆、栈

摘要：栈底是固定的，而栈顶浮动的如果栈中元素个数为零则被称为空栈。入栈将数据保存到栈顶。链栈链栈是指栈的链式存储结构，是没有附加头节点的运算受限的单链表，栈顶指针是链表的头指针。一、喜欢单挑线性表 1.线性表的特性线性表是一个线性结构，它是一个含有n≥0个节点的有限序列。在节点中，有且仅有一个开始节点没有前驱并有一个后继节点，有且仅有一个终端节点没有后继并有一个前驱节点。其他的节点都有且...

huaixiaoz 2019-06-27 14:11 评论0 收藏0
基本算法学习之(二)快速排序与归并排序

摘要：快速排序看名字知特点就是快效率高它是处理大数据最快的排序算法之一奇妙的记忆点内排序不稳定基本思想通过一趟排序把待排序记录分为独立的两部分其中一部分记录的关键字都比另一部分的关键字笑则分别对两部分继续进行排序以达到整个序列有序自己的理解其实就快速排序(Quick Sort) 看名字知特点,就是快,效率高.它是处理大数据最快的排序算法之一.奇妙的记忆点: 内排序不稳定基本思想通...

Songlcy 2019-08-20 11:12 评论0 收藏0
区块链学习之分布式系统核心问题（四）

摘要：区块链系统首先是一个分布式系统，分布式系统的核心问题包括一致性共识一致性问题一致性问题是分布式领域最为基础也是最重要的问题。算法与算法问题是指分布式系统中存在故障，但不存在恶意节点的场景即可能消息丢失或重复，但无错误消息下的共识达成问题。区块链系统首先是一个分布式系统，分布式系统的核心问题包括一致性、共识一致性问题一致性问题是分布式领域最为基础也是最重要的问题。如果分布式系统能实...

Heier 2019-06-27 18:27 评论0 收藏0
深度学习之图像视频压缩技术

摘要：目前，其已经在人脸识别等领域证明了它的强大能力，有理由相信在不久的将来，深度学习技术将为图像视频压缩领域带来更大的突破。说到图像压缩算法，最典型的就是JPEG、JPEG2000等。showImg(https://segmentfault.com/img/bV1ObD?w=539&h=412); 其中JPEG 采用的是以离散余弦转换(Discrete Cosine Transform)...

Salamander 2019-06-21 16:16 评论0 收藏0