排序算法实现和性能分析

雨点打透心脏的1/2处 2023-07-06 05:00 32阅读 0赞

## 排序算法 ##

[冒泡排序、选择排序、插入排序][Link 1]  
[希尔排序][Link 2]  
[归并排序、快速排序][Link 3]  
[基数排序][Link 4]

## 性能 ##

<table> 
 <thead> 
  <tr> 
   <th>排序算法</th> 
   <th>最好时间复杂度</th> 
   <th>最坏时间复杂度</th> 
   <th>平均时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>稳定性</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>冒泡排序</td> 
   <td>O(n)</td> 
   <td>O(n^ 2)</td> 
   <td>O(n^2)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>选择排序</td> 
   <td>O(n^ 2)</td> 
   <td>O(n^ 2)</td> 
   <td>O(n^2)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>O(n)</td> 
   <td>O(n^ 2)</td> 
   <td>O(n^2)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td>具体和增量序列有关 O(n^ (1.3~2)）</td> 
   <td></td> 
   <td></td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>nO(log n)</td> 
   <td>O(n^ 2)</td> 
   <td>nO(log n)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td>nO(log n)</td> 
   <td>nO(log n)</td> 
   <td>nO(log n)</td> 
   <td>O(n)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>基数排序</td> 
   <td>O(d(r+n))</td> 
   <td>O(d(r+n))</td> 
   <td>O(d(r+n))</td> 
   <td>O(n+r)</td> 
   <td>稳定</td> 
  </tr> 
 </tbody> 
</table>

> n代表待排序数据个数，d表示关键码个数，r表示关键码的取值范围

[Link 1]: https://blog.csdn.net/IT_10/article/details/103328179
[Link 2]: https://blog.csdn.net/IT_10/article/details/104333204
[Link 3]: https://blog.csdn.net/IT_10/article/details/103334997
[Link 4]: https://blog.csdn.net/IT_10/article/details/104340480