排序算法总结

比较排序算法

定义：

英语：Comparison sort）是排序算法的一种，通过一个抽象的内容比较操作（通常是“小于或等于”操作）来确定两个元素中哪个应该放在序列前面[3]。

比较排序算法特例

1. 快速排序
2. 堆排序
3. 归并排序
4. 希尔排序
5. 插入排序
6. 选择排序
7. 冒泡排序

非比较排序算法特例

1. 基数排序
2. 计数排序
3. 桶排序

性能限制和优势

性能限制

1. 在最差情况下，任何一种比较排序至少需要 O(n*log n)比较操作
2. 归并排序，堆排序在他们必须比较的次数上是渐进最优的，虽然这忽略了其他的操作
3. 三种非比较排序算法通过非比较操作能在O(n)完成，这使他们能够回避 O(n*log n)这个下界（假设元素是定值）

优势

1. 比较排序能对各种数据类型进行排序，并且可以很好地控制一个序列如何被排序
2. 比较排序可以更好地适应复杂数据结构的顺序，例如浮点数
3. 非比较排序对数据类型的要求更严格。

总结

这种灵活性和上述比较排序在现代计算机的执行效率一起导致了比较排序被更多地应用在了大多数实际工作中。

插入排序：

直接插入排序的定义：

依次从数组索引开始选择元素，与当前元素之前的数据一一比较，找到比当前元素小并且后一个元素比当前元素大，然后放入此位置，结束一轮排序。然后选择下一个索引数据继续比较插入指定位置。选择某个元素，此元素之前的数据是已经排好了序的，所以只要找到比当前元素小的就可以确定位置。

比较排序和非比较排序的选择

问题：基数排序是否比基于比较的排序算法（如快速排序）更好呢？

答案：① 通常情况，如果b=O(lgn)，而且我们选择r约等于lgn，则基数排序的运行时间为Θ(n)。这一结果看上去要比快速排序的期望运行时间代价Θ(nlgn)更好一些。
② 隐含在Θ符号背后的常数项因子是不同的。在处理n个关键字时，尽管基数排序执行的循环轮数会比快速排序要少，但每一轮它所耗费的时间要长得多。
③排序算法的选择依赖于具体实现和底层硬件的特性以及输入数据的特征，（例如，快速排序通常可以比基数排序更有效地使用硬件的缓存）。
④利用计数排序作为中间稳定排序的基数排序不是原址排序，而很多Θ(nlgn)时间的比较排序是原址排序。
⑤ 因此，当主存的容量比较宝贵时，我们可能会更倾向于像快速排序这样的原址排序算法。

原址排序定义：如果输入数组中仅有常数个元素需要在排序过程中存储至辅助数组，则称排序算法是原址的（in place）

排序算法的应用[2]

排序就是将一组对象按照某种逻辑顺序重新排列的过程。比如信用卡账单中的交易是按照日期排序的——这种排序很可能使用了某种排序算法。
在计算时代早期，大家普遍认为30%的计算周期都用在了排序上，今天这个比例可能降低了，大概是因为现在的排序算法更加高效。现在这个时代数据可以说是无处不在，而整理数据的第一步往往就是进行排序。所有的计算机系统都实现了各种排序算法以供系统和用户使用。即使你只是使用标准库中的排序函数，学习排序算法仍然有很大的实际意义：

排序算法往往是我们解决其他问题的第一步
排序算法有助于我们理解其他算法
算法在公司面试中占有很大比例，排序算法作为其中的重要组成部分，我们理所当然要学好了。　　
另外，更重的是下面介绍的这些算法都很经典，优雅而且高效，学习其中的精髓对自己提高自己的编程能力也有很大的帮助。　　
排序在商业数据处理和现代科学计算中有很重要的地位，它能够应用于事务处理,组合优化，天体物理学，分子动力学，语言学，基因组学，天气预报和很多其他领域。例如快速排序被誉为20世纪科学和工程领域的十大算法之一。

应用场景[1]

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；
(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
　快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
　堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
　若要求排序稳定，则可选用归并排序。但前面介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子序列，然后再两两归并之。因为直接插入排序是稳定 的，所以改进后的归并排序仍是稳定的。

[1] 各类排序算法比较和应用场景
[2] 排序算法（Java）——那些年面试常见的排序算法
[3] 比较排序