堆排序算法(堆排序和快速排序对比)

堆排序算法(堆排序和快速排序对比)

快速排序与堆排序介绍与对比 ——基于JavaScript

  在多种排序方法中,快速排序是基于内部比较的排序方法中被公认最好的一种:从算法效率角度来看:快速排序的平均时间复杂度为O(nlogn),常数级指令比较少;从CPU架构方面来看:快速排序的inner loop中,进行比较的元素往往集中在一个区域段,cache不需要过于频繁的从内存中抓取新数据给ALU,对各类型CPU架构都相当友好。所以当大家需要处理涉及浮点数据的排序时,快排基本是最优的选择(脸不是特别黑的话XD)。

  同样属于基于比较的内容排序方法,堆排序也位列排序算法的第一集团。从算法效率角度看,其时间复杂度为O(nlogn),并不输快排,但比较遗憾的是:堆排序在移除堆顶元素时,将堆顶元素与堆底元素互换位置,这意味着将堆顶元素换成一个大概率很小的元素,然后再让这个大概率很小的新堆顶元素向下比较,以期构造出一个最大堆,这个过程中充斥着非必要的比较,拖累了堆排序的效率;而从cache角度看:堆排序每次操作的元素数据跨度可能非常大,无形中增添了cache的需求,当元素数量非常多时,cache就需要反复从内存中抓取数据了,简单来讲,就是堆排序相对于快速排序的Locality of reference非常差。

  但这不意味着堆排序没有价值:在快排被数据针对时,时间复杂度最差能到O(n2),而堆排序难以被针对,其最差时间复杂度仍是O(nlogn);快排不能在排序过程中稳定得到指定序列的元素,一切都需要排序完成才可以知晓,但堆排可以指定一个序列位置,在拿到序列位置元素后大可以中止排序,所以快排虽然在速度上打败了堆排,但在功能上并不能碾压堆排。堆排序算法(堆排序和快速排序对比)堆排序算法(堆排序和快速排序对比)wiki搬运图~

  快速排序属于冒泡排序的超级魔改,是图灵奖得者Tony Hoare – Wikipedia的得意之作。其基本思想是:在要排序的数组中选取一个锚点,通过遍历数组元素与锚点进行比较,将小于锚点值的元素放到锚点的左边,而相应地大于锚点值的元素放到锚点右边,inner loop完成后,锚点本身的位置得以确认,此时再对锚点左和锚点右进行同样的递归,而递归的边界即是数组的长度小于2(也就是只剩一个锚外无其他元素了)。

  堆排序算法(堆排序和快速排序对比)堆排序算法(堆排序和快速排序对比)wiki搬运~

  堆排序是另一位图灵奖大牛Robert W. Floyd – Wikipedia的智慧结晶。其思路是:利用原有数组模拟一个完全二叉树,再将父节点及左右子节点看作一个基本堆;首先从最后面的堆开始建立堆积结构(即堆顶不小于堆底中任意一个),逐渐遍历到顶部的堆,使得整个树形成堆积结构;然后将堆顶元素(此时的堆顶元素即数组中最大值)与堆底元素(数组尾部)互换位置,并封存这个尾部位置;再后从互换后的堆顶元素递归重新调整最大堆,递归边界为数组剩余元素小于2,无法再形成堆结构。

  刘未鹏 | Mind Hacks——数学之美番外篇:快排为什么那么快

  Quicksort – Wikipedia

  Heapsort – Wikipedia

  Algorithm | bubkoo

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
转载请注明出处: https://daima100.com/23566.html

(0)
上一篇 2023-10-24
下一篇 2023-10-24

相关推荐