几种常见的算法比较

谁践踏了优雅 2021-09-23 03:26 494阅读 0赞

![这里写图片描述][SouthEast]  
**排序算法总结：**

时间复杂度：

\-平方阶O(n2)的排序：各类简单排序、直接插入、直接选择、冒泡排序  
\- 线性对数O(nlg2n)排序：快速排序、堆排序和归并排序  
\- O(n1+)排序：为介于0-1之间的常数：希尔排序  
\- 线性O(n)排序：基数排序、桶排序、箱排序

空间复杂度：

*  空间复杂度为O(1)：冒泡排序、选择排序、直接插入排序、折半插入排序、希尔排序、堆排序

稳定性：

*  稳定的排序算法有：冒泡排序、直接插入排序、折半插入排序、归并排序、基数排序和计数排序

**特别注意：**  
1. 当输入数组有序或者基本有序时，直接插入和冒泡排序将大大减少比较次数和移动次数。时间复杂度降为O(n)。  
2. 快速排序恰恰相反，当输入数组基本有序时，将退化为冒泡排序，时间复杂度增加到O(n2)  
3. 输入数组有序与否对简单排序、堆排序、归并排序、和基数排序的时间复杂度影响不大。

常用算法比较图：  
![这里写图片描述][2016-07-15_E5_B8_B8_E7_94_A8_E6_8E_92_E5_BA_8F_E7_AE_97_E6_B3_95.png]

--------------------

原文链接：

## [https://itimetraveler.github.io/2017/07/18/%E5%85%AB%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E4%B8%8Ejava%E5%AE%9E%E7%8E%B0/][https_itimetraveler.github.io_2017_07_18_E5_85_AB_E5_A4_A7_E6_8E_92_E5_BA_8F_E7_AE_97_E6_B3_95_E6_80_BB_E7_BB_93_E4_B8_8Ejava_E5_AE_9E_E7_8E_B0] ##

[SouthEast]: /images/20210923/49ff4a0b9169406594aa6ab16f9f5134.png
[2016-07-15_E5_B8_B8_E7_94_A8_E6_8E_92_E5_BA_8F_E7_AE_97_E6_B3_95.png]: /images/20210923/74cb5a45d6db408b9299bd663974d2d6.png
[https_itimetraveler.github.io_2017_07_18_E5_85_AB_E5_A4_A7_E6_8E_92_E5_BA_8F_E7_AE_97_E6_B3_95_E6_80_BB_E7_BB_93_E4_B8_8Ejava_E5_AE_9E_E7_8E_B0]: https://itimetraveler.github.io/2017/07/18/%E5%85%AB%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E4%B8%8Ejava%E5%AE%9E%E7%8E%B0/