大家好，我是考100分的小小码 ，祝大家学习进步，加薪顺利呀。今天说一说堆排序算法（堆排序和快速排序对比）,希望您对编程的造诣更进一步.
快速排序与堆排序介绍与对比 ——基于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
