既然快速排序已经是非常好非常快了,为什么还要堆排序?

cdsfiui

都是O(nlgn)
如果说快速排序需要用到递归，最坏情况会退化成O(n*n)，那么干脆就都用堆排序好了。

这两种排序各有什么优势吗? 还是说，应用场景不同? 常数因子不同?

windoze

堆排序比较和交换次数比快速排序多，所以平均而言比快速排序慢，也就是常数因子比快速排序大，如果你需要的是“排序”，那么绝大多数场合都应该用快速排序而不是其它的O(nlogn)算法。

但有时候你要的不是“排序”，而是另外一些与排序相关的东西，比如最大/小的元素，topK之类，这时候堆排序的优势就出来了。用堆排序可以在N个元素中找到top K，时间复杂度是O(N log K)，空间复杂的是O(K)，而快速排序的空间复杂度是O(N)，也就是说，如果你要在很多元素中找很少几个top K的元素，或者在一个巨大的数据流里找到top K，快速排序是不合适的，堆排序更省地方。

另外一个适合用heap的场合是优先队列，需要在一组不停更新的数据中不停地找最大/小元素，快速排序也不合适。

此外merge sort之类算法虽说也是O(nlogn)，但一般都只在一些很特殊的场合才会用，比如N-way merge，可以把N个已经排好序的数据流合并成一个排好序的数据流，当然这个算法其实严格说并不能算是merge sort，只是用了其中的几个步骤，不过思路是一样的。

基于交换的排序常用的就这么几种（什么冒泡选择之类的你可以无视了），其它的不基于交换的排序比如radix sort、bucket sort之类由于应用场合比较特殊，一般很少用到。

fender0107401

如果算法A在所有方面都比B好话，那么可以忽略B。

但是多数情况下，A和B都是在某一方面比对方好。

lxyscls

猫哥，还有什么是你不会的吗？

linux_c_py_php

如果单纯是排序来看，两者没有什么差异。

他们的区别在于其他用途，例如快排无法高效的动态增删数据，而堆是树型结构，支持动态的增删数据，通常用来做定时器等，通常可以和平衡树互相取代。

action08

跟红黑树的道理一样，实时系统，堆排序在特定的场合，实时性是非常不错的



建议你看原版的算法导论，一切一目了然

爻易

时间占用只是因素之一，还有空间占用，是否稳定排序等等需求。

需求的多样性决定了算法的多样性！

dorodaloo

回复 2# windoze


windoz 赞一个!
还有什么是你不会的吗？

cdsfiui

回复 5# linux_c_py_php


    嗯，这个非常好！