常见排序算法总结

• • 排序算法汇总
  • 排序算法对比
  • 小结

排序算法汇总

最近对排序算法进行了一些复习，单独对常见的几种排序算法进行了整理总结，汇总如下：

• 算法基础（三）– 归并排序及其应用
• 算法基础（四）– 快速排序要点整理
• 算法基础（五）– 堆结构与堆排序
• 算法基础（六）– 桶排序：计数排序与基数排序

这里再列上很早之前写的几篇排序相关文章，算是进行一个汇总：

1. 插入排序–直接插入排序与希尔排序
2. 交换排序–冒泡排序与快速排序
3. 选择排序–直接选择与堆排序
4. 拜托，面试不要问我比较排序了——一文搞懂比较排序
5. 排序算法——归并排序
6. 非比较排序之计数排序/桶排序
7. 分配排序之基数排序

到这里，算是对常见的每一个排序算法有了比较充分的认识，但还缺少一些对他们之间的横向对比。

排序算法对比

算法之间的对比常见的有时间复杂度、额外空间复杂度，对于排序算法来说，还有一个稳定性指标：指同样大小的样本再排序之后不会改变相对次序，如果没有改变，我们称排序算法具有稳定性。

对于基础类型的排序，比如整型，稳定性是没有意义的；而对于非基础类型，稳定性有重要意义。

常见排序算法之间的对比总结如下表：

我们知道，计数、基数排序是非比较的排序方式，对样本数据有严格的规定。
基于比较的排序中，选择、冒泡、插入排序的时间复杂度都相对较高，因此平常不常用。而归并、快排、堆排序都有其各自的特点，适用于不同场景，基于此表格的具体总结如下：

1. 不基于比较的排序对样本数据有严格的要求，不易于改写；
2. 基于比较的排序，规定好两个样本如何比较大小，可直接复用；
3. 基于比较的排序，时间复杂度的极限是O(N*logN)；
4. 时间复杂度O(N*logN)、额外空间复杂度低于O(N)、且稳定的基于比较的排序不存在；
5. 为了绝对的速度选快排、为了省空间选堆排、为了稳定性选归并。

小结

到这里，算是对排序算法做了一个简短的总结，后面继续我的算法旅程，我会继续分享更多算法学习过程中的记录、总结，感谢大家的持续关注。

欢迎关注我的公众号【CoolWrite】，了解更多内容：