常用排序算法复杂度和稳定性总结

桃扇骨 2022-02-12 23:50 272阅读 0赞

<table> 
 <thead> 
  <tr> 
   <th>排序算法</th> 
   <th>平均时间复杂度</th> 
   <th>最好情况</th> 
   <th>最坏情况</th> 
   <th>空间复杂度</th> 
   <th>稳定性</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>冒泡排序</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>选择排序</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td>O(nlogn)~O(n<sup>2</sup>)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(n)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(logn)~O(n)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>计数排序</td> 
   <td>O(n+k)</td> 
   <td>O(n+k)</td> 
   <td>O(n+k)</td> 
   <td>O(k)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>桶排序</td> 
   <td>O(n+k)</td> 
   <td>O(n+k)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n+k)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>基数排序</td> 
   <td>O(n×k)</td> 
   <td>O(n×k)</td> 
   <td>O(n×k)</td> 
   <td>O(n+k)</td> 
   <td>稳定</td> 
  </tr> 
 </tbody> 
</table>

**堆选归集与初始序列无关**