排序概述 gaunthan Posted on Jan 5 2017 ? Sorting ? ## 分类 排序有**内部**排序和**外部**排序。内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 下图为各大排序算法的归类:  ## 复杂度 注意,表中冒泡排序最好情况为$O(n)$是基于已改进的冒泡排序算法,传统冒泡排序各种情况的时间复杂度均为$O(n^2)$。另外,快速排序平均需要占用$O(logn)$的栈空间(无论是隐式的递归栈还是显式的用户栈),最坏情况下将占用$O(n)$的空间。注意下图中关于快速排序的空间复杂度的说明是有误的……  你可能会疑惑为什么归并排序的空间复杂度是$O(1)$,按理来说应该是$O(n)$,毕竟我们需要使用一个临时数组。实际上,这个临时数组是可以避免的。通过使用“翻手准则”,我们可以在原地实现合并。具体实现可以阅读我另一篇文章:[归并排序(Merge sort)](http://leanote.com/blog/post/5783b76fab644133ed0088cc)。 ## 排序算法的选择 * 当n较小,直接插入排序具有比较好的性能; * 当n较大,则应采用时间复杂度为$O(nlogn)$的排序方法:快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短。 ## References - [八大排序算法](http://blog.csdn.net/hguisu/article/details/7776068)。 - [各种排序算法时间复杂度、稳定性、初始序列是否对元素比较次数有关](http://blog.csdn.net/hr10707020217/article/details/10581371)。 赏 Wechat Pay Alipay 数据结构:二叉查找树 MS Word 设置页码从任意页开始