排序概述 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 设置页码从任意页开始
