java排序算法总结

野性酷女 2022-02-17 10:11 407阅读 0赞

### java排序算法总结 ###

排序，这是一个很古老但是又很经典的问题，世界上有很多中优秀排序算法的实现，在这里，我总结了其他比较常用的几种排序算法

#### 1.java排序算法一览 ####

1.  [冒泡排序和基数排序][Link 1]
2.  [桶排序和计数排序][Link 2]
3.  [归并排序和快速排序][Link 3]
4.  [堆排序][Link 4]
5.  [插入排序和希尔排序][Link 5]

#### 2.分类 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70]

#### 3.比较 ####

**1.时间复杂度比较**

<table> 
 <thead> 
  <tr> 
   <th>算法</th> 
   <th>乱序时间复杂度</th> 
   <th>有序时间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>插入排序</td> 
   <td>O(N^2)</td> 
   <td>O(N)</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td>O(N^2)</td> 
   <td>O(N)</td> 
  </tr> 
  <tr> 
   <td>冒泡排序</td> 
   <td>O(N^2)</td> 
   <td>O(N)</td> 
  </tr> 
  <tr> 
   <td>基数排序</td> 
   <td>O(N)</td> 
   <td>O(N)</td> 
  </tr> 
  <tr> 
   <td>桶排序</td> 
   <td>O(N)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>计数排序</td> 
   <td>O(N)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td>O(NlogN)</td> 
   <td>O(NlogN)</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>O(NlogN)</td> 
   <td>O(N^2)</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O(NlogN)</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

**2.空间复杂度比较**

<table> 
 <thead> 
  <tr> 
   <th>算法</th> 
   <th>空间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>插入排序</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>冒泡排序</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>基数排序</td> 
   <td>O(N)</td> 
  </tr> 
  <tr> 
   <td>桶排序</td> 
   <td>O(N+M) M是额外辅助空间（桶数量）</td> 
  </tr> 
  <tr> 
   <td>计数排序</td> 
   <td>O(N)</td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td>O(N)</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O(1)</td> 
  </tr> 
 </tbody> 
</table>

[Link 1]: https://blog.csdn.net/weixin_41922289/article/details/89379901
[Link 2]: https://blog.csdn.net/weixin_41922289/article/details/89354587
[Link 3]: https://blog.csdn.net/weixin_41922289/article/details/89334243
[Link 4]: https://blog.csdn.net/weixin_41922289/article/details/89285521
[Link 5]: https://blog.csdn.net/weixin_41922289/article/details/89151737
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70]: /images/20220217/12bbee49645c4240a5efc53aef05e8f8.png