《十大排序算法》文章集锦

深碍√TFBOYSˉ_ 2022-12-23 14:27 101阅读 0赞

###### 术语说明 ######

> 时间复杂度 ：耗费的时间。  
> 空间复杂度 ：所需内存的大小。  
> 稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。  
> 不稳定 ：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面。

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

**注：**  
n: 数据规模。  
k: “桶”的个数。

> 冒泡排序、希尔排序、插入排序、选择排序、快速排序、归并排序和堆排序属于比较排序 。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置 。

> 计数排序、桶排序和基数排序属于非比较排序 。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr\[i\]之前有多少个元素，则唯一确定了arr\[i\]在排序后数组中的位置 。

### 十大排序算法（Java实现）文章集锦 ###

《排序算法》**冒泡排序**：[https://blog.csdn.net/weixin\_44547599/article/details/98636350][https_blog.csdn.net_weixin_44547599_article_details_98636350]

《排序算法》**希尔排序**：[https://blog.csdn.net/weixin\_44547599/article/details/98656480][https_blog.csdn.net_weixin_44547599_article_details_98656480]

《排序算法》**插入排序**：[https://blog.csdn.net/weixin\_44547599/article/details/108768958][https_blog.csdn.net_weixin_44547599_article_details_108768958]

《排序算法》**选择排序**：[https://blog.csdn.net/weixin\_44547599/article/details/109093042][https_blog.csdn.net_weixin_44547599_article_details_109093042]

《排序算法》**快速排序**：[https://blog.csdn.net/weixin\_44547599/article/details/109310997][https_blog.csdn.net_weixin_44547599_article_details_109310997]

《排序算法》**归并排序**：[https://blog.csdn.net/weixin\_44547599/article/details/109515510][https_blog.csdn.net_weixin_44547599_article_details_109515510]

《排序算法》**堆排序**：[https://blog.csdn.net/weixin\_44547599/article/details/109777007][https_blog.csdn.net_weixin_44547599_article_details_109777007]

《排序算法》**计数排序**：[https://blog.csdn.net/weixin\_44547599/article/details/110000205][https_blog.csdn.net_weixin_44547599_article_details_110000205]

《排序算法》**桶排序**：[https://blog.csdn.net/weixin\_44547599/article/details/110118720][https_blog.csdn.net_weixin_44547599_article_details_110118720]

《排序算法》**基数排序**：[https://blog.csdn.net/weixin\_44547599/article/details/110132194][https_blog.csdn.net_weixin_44547599_article_details_110132194]

[https_blog.csdn.net_weixin_44547599_article_details_98636350]: https://blog.csdn.net/weixin_44547599/article/details/98636350
[https_blog.csdn.net_weixin_44547599_article_details_98656480]: https://blog.csdn.net/weixin_44547599/article/details/98656480
[https_blog.csdn.net_weixin_44547599_article_details_108768958]: https://blog.csdn.net/weixin_44547599/article/details/108768958
[https_blog.csdn.net_weixin_44547599_article_details_109093042]: https://blog.csdn.net/weixin_44547599/article/details/109093042
[https_blog.csdn.net_weixin_44547599_article_details_109310997]: https://blog.csdn.net/weixin_44547599/article/details/109310997
[https_blog.csdn.net_weixin_44547599_article_details_109515510]: https://blog.csdn.net/weixin_44547599/article/details/109515510
[https_blog.csdn.net_weixin_44547599_article_details_109777007]: https://blog.csdn.net/weixin_44547599/article/details/109777007
[https_blog.csdn.net_weixin_44547599_article_details_110000205]: https://blog.csdn.net/weixin_44547599/article/details/110000205
[https_blog.csdn.net_weixin_44547599_article_details_110118720]: https://blog.csdn.net/weixin_44547599/article/details/110118720
[https_blog.csdn.net_weixin_44547599_article_details_110132194]: https://blog.csdn.net/weixin_44547599/article/details/110132194