数据结构（十六）排序

Love The Way You Lie 2022-04-15 06:10 140阅读 0赞

## 排序算法 ##

### 0. 前言 ###

本来准备自己写，无意间看到一位大佬的博文…大家还是移步吧  
[推荐一套自己开发的算法演示工具][Link 1]

### 1. 总结 ###

<table> 
 <thead> 
 <tr> 
 <th>排序方法</th> 
 <th>平均时间复杂度</th> 
 <th>最坏时间复杂度</th> 
 <th>额外空间复杂度</th> 
 <th>稳定性</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>简单选择排序</td> 
 <td>O( N 2 N^2 N2)</td> 
 <td>O( N 2 N^2 N2)</td> 
 <td>O( 1 1 1)</td> 
 <td>不稳定</td> 
 </tr> 
 <tr> 
 <td>冒泡排序</td> 
 <td>O( N 2 N^2 N2)</td> 
 <td>O( N 2 N^2 N2)</td> 
 <td>O( 1 1 1)</td> 
 <td>稳定</td> 
 </tr> 
 <tr> 
 <td>直接插入排序</td> 
 <td>O( N 2 N^2 N2)</td> 
 <td>O( N 2 N^2 N2)</td> 
 <td>O( 1 1 1)</td> 
 <td>稳定</td> 
 </tr> 
 <tr> 
 <td>希尔排序</td> 
 <td>O( N d N^d Nd)</td> 
 <td>O( N 2 N^2 N2)</td> 
 <td>O( 1 1 1)</td> 
 <td>不稳定</td> 
 </tr> 
 <tr> 
 <td>堆排序</td> 
 <td>O( N l o g N NlogN NlogN)</td> 
 <td>O( N l o g N NlogN NlogN)</td> 
 <td>O( 1 1 1)</td> 
 <td>不稳定</td> 
 </tr> 
 <tr> 
 <td>快速排序</td> 
 <td>O( N l o g N NlogN NlogN)</td> 
 <td>O( N 2 N^2 N2)</td> 
 <td>O( l o g N logN logN)</td> 
 <td>不稳定</td> 
 </tr> 
 <tr> 
 <td>归并排序</td> 
 <td>O( N l o g N NlogN NlogN)</td> 
 <td>O( N l o g N NlogN NlogN)</td> 
 <td>O(N)</td> 
 <td>稳定</td> 
 </tr> 
 <tr> 
 <td>基数排序</td> 
 <td>O(P(N+B))</td> 
 <td>O(P(N+B))</td> 
 <td>O(N+B)</td> 
 <td>稳定</td> 
 </tr> 
 </tbody> 
</table>

### 2. 各种排序算法比较 ###

[《数据结构》09-排序1 排序][09-_1]

[Link 1]: https://blog.csdn.net/qq_31116753/article/details/84076734
[09-_1]: https://blog.csdn.net/liyuanyue2017/article/details/84325540