堆排序 快排 使用场景

堆排序和快速排序的比较

堆排序比较和交换次数比快速排序多，所以平均而言比快速排序慢，也就是常数因子比快速排序大，如果你需要的是“排序”，那么绝大多数场合都应该用快速排序而不是其它的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之类由于应用场合比较特殊，一般很少用到。

堆排序原理

参考我之前的这一篇