Chinaunix

标题: 既然快速排序已经是非常好非常快了,为什么还要堆排序? [打印本页]

作者: cdsfiui 时间: 2015-12-29 22:37
标题: 既然快速排序已经是非常好非常快了,为什么还要堆排序?
都是O(nlgn)
如果说快速排序需要用到递归，最坏情况会退化成O(n*n)，那么干脆就都用堆排序好了。

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

作者: windoze 时间: 2015-12-29 23:11
堆排序比较和交换次数比快速排序多，所以平均而言比快速排序慢，也就是常数因子比快速排序大，如果你需要的是“排序”，那么绝大多数场合都应该用快速排序而不是其它的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 时间: 2015-12-30 09:08
如果算法A在所有方面都比B好话，那么可以忽略B。

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

作者: lxyscls 时间: 2015-12-30 10:37
猫哥，还有什么是你不会的吗？

作者: linux_c_py_php 时间: 2015-12-30 11:39
如果单纯是排序来看，两者没有什么差异。

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

作者: action08 时间: 2015-12-30 13:10
跟红黑树的道理一样，实时系统，堆排序在特定的场合，实时性是非常不错的

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

作者: 爻易 时间: 2016-01-02 08:20
时间占用只是因素之一，还有空间占用，是否稳定排序等等需求。

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

作者: dorodaloo 时间: 2016-01-02 10:13
回复 2# windoze

windoz

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

作者: cdsfiui 时间: 2016-01-12 22:02
回复 5# linux_c_py_php

嗯，这个非常好！

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)