常见排序算法的性能对比

r囧r小猫 2022-10-25 14:28 103阅读 0赞

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>时间复杂度</th> 
   <th>空间复杂度</th> 
   <th align="center">可否实现稳定性</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>选择</td> 
   <td><span><span><span> O ( N 2 ) O(N^2) </span><span><span><span style="height: 1.06411em; vertical-align: -0.25em;"></span><span style="margin-right: 0.02778em;">O</span><span>(</span><span><span style="margin-right: 0.10903em;">N</span><span><span><span><span style="height: 0.814108em;"><span style="top: -3.063em; margin-right: 0.05em;"><span style="height: 2.7em;"></span><span><span>2</span></span></span></span></span></span></span></span><span>)</span></span></span></span></span></td> 
   <td><span><span><span> O ( 1 ) O(1) </span><span><span><span style="height: 1em; vertical-align: -0.25em;"></span><span style="margin-right: 0.02778em;">O</span><span>(</span><span>1</span><span>)</span></span></span></span></span></td> 
   <td align="center">No</td> 
  </tr> 
  <tr> 
   <td>冒泡</td> 
   <td><span><span><span> O ( N 2 ) O(N^2) </span><span><span><span style="height: 1.06411em; vertical-align: -0.25em;"></span><span style="margin-right: 0.02778em;">O</span><span>(</span><span><span style="margin-right: 0.10903em;">N</span><span><span><span><span style="height: 0.814108em;"><span style="top: -3.063em; margin-right: 0.05em;"><span style="height: 2.7em;"></span><span><span>2</span></span></span></span></span></span></span></span><span>)</span></span></span></span></span></td> 
   <td><span><span><span> O ( 1 ) O(1) </span><span><span><span style="height: 1em; vertical-align: -0.25em;"></span><span style="margin-right: 0.02778em;">O</span><span>(</span><span>1</span><span>)</span></span></span></span></span></td> 
   <td align="center">Yes</td> 
  </tr> 
  <tr> 
   <td>插入</td> 
   <td><span><span><span> O ( N 2 ) O(N^2) </span><span><span><span style="height: 1.06411em; vertical-align: -0.25em;"></span><span style="margin-right: 0.02778em;">O</span><span>(</span><span><span style="margin-right: 0.10903em;">N</span><span><span><span><span style="height: 0.814108em;"><span style="top: -3.063em; margin-right: 0.05em;"><span style="height: 2.7em;"></span><span><span>2</span></span></span></span></span></span></span></span><span>)</span></span></span></span></span></td> 
   <td><span><span><span> O ( 1 ) O(1) </span><span><span><span style="height: 1em; vertical-align: -0.25em;"></span><span style="margin-right: 0.02778em;">O</span><span>(</span><span>1</span><span>)</span></span></span></span></span></td> 
   <td align="center">Yes</td> 
  </tr> 
  <tr> 
   <td>归并</td> 
   <td><span><span><span> O ( N log ⁡ N ) O(N\log N) </span><span><span><span style="height: 1em; vertical-align: -0.25em;"></span><span style="margin-right: 0.02778em;">O</span><span>(</span><span style="margin-right: 0.10903em;">N</span><span style="margin-right: 0.166667em;"></span><span>lo<span style="margin-right: 0.01389em;">g</span></span><span style="margin-right: 0.166667em;"></span><span style="margin-right: 0.10903em;">N</span><span>)</span></span></span></span></span></td> 
   <td><span><span><span> O ( N ) O(N) </span><span><span><span style="height: 1em; vertical-align: -0.25em;"></span><span style="margin-right: 0.02778em;">O</span><span>(</span><span style="margin-right: 0.10903em;">N</span><span>)</span></span></span></span></span></td> 
   <td align="center">Yes</td> 
  </tr> 
  <tr> 
   <td>快速</td> 
   <td><span><span><span> O ( N log ⁡ N ) O(N\log N) </span><span><span><span style="height: 1em; vertical-align: -0.25em;"></span><span style="margin-right: 0.02778em;">O</span><span>(</span><span style="margin-right: 0.10903em;">N</span><span style="margin-right: 0.166667em;"></span><span>lo<span style="margin-right: 0.01389em;">g</span></span><span style="margin-right: 0.166667em;"></span><span style="margin-right: 0.10903em;">N</span><span>)</span></span></span></span></span></td> 
   <td><span><span><span> O ( log ⁡ N ) O(\log N) </span><span><span><span style="height: 1em; vertical-align: -0.25em;"></span><span style="margin-right: 0.02778em;">O</span><span>(</span><span>lo<span style="margin-right: 0.01389em;">g</span></span><span style="margin-right: 0.166667em;"></span><span style="margin-right: 0.10903em;">N</span><span>)</span></span></span></span></span></td> 
   <td align="center">No</td> 
  </tr> 
  <tr> 
   <td>堆</td> 
   <td><span><span><span> O ( N log ⁡ N ) O(N\log N) </span><span><span><span style="height: 1em; vertical-align: -0.25em;"></span><span style="margin-right: 0.02778em;">O</span><span>(</span><span style="margin-right: 0.10903em;">N</span><span style="margin-right: 0.166667em;"></span><span>lo<span style="margin-right: 0.01389em;">g</span></span><span style="margin-right: 0.166667em;"></span><span style="margin-right: 0.10903em;">N</span><span>)</span></span></span></span></span></td> 
   <td><span><span><span> O ( 1 ) O(1) </span><span><span><span style="height: 1em; vertical-align: -0.25em;"></span><span style="margin-right: 0.02778em;">O</span><span>(</span><span>1</span><span>)</span></span></span></span></span></td> 
   <td align="center">No</td> 
  </tr> 
 </tbody> 
</table>

### 排序算法的稳定性 ###

同样值的个体之间，如果不因为排序而改变相对次序，就是这个排序是有稳定 性的；否则就没有。

*  不具备稳定性的排序
    
     *  选择排序、快速排序、堆排序
 *  具备稳定性的排序
    
     *  冒泡排序、插入排序、归并排序、一切桶排序思想下的排序

目前没有找到时间复杂度 O ( N ∗ l o g N ) O(N\*logN) O(N∗logN)，额外空间复杂度 O ( 1 ) O(1) O(1)，又**稳定**的排序。

发表评论取消回复

表情：

评论列表（有 0 条评论，103人围观）

还没有评论，来说两句吧...

相关阅读

相关 [排序算法] 常见的排序算法

前言 1.冒泡排序 2.选择排序 3.插入排序 4希尔排序 5.归并排序 6.快速排序前言在实际需求中，我们可能要

雨点打透心脏的1/2处/ 2023年09月29日 14:29/ 0 赞/ 203 阅读

相关 java常见的排序算法_Java中常见的排序算法

Sorting algorithms are an important part of managing data. At Cprogramming.com, we offer

我不是女神ヾ/ 2022年11月04日 00:45/ 0 赞/ 152 阅读

相关常见排序算法的性能对比

<table> <thead> <tr> <th></th> <th>时间复杂度</th> <th>空间复杂度</th> <th al

r囧r小猫/ 2022年10月25日 14:28/ 0 赞/ 104 阅读

相关快速排序的几种常见实现及其性能对比

快速排序的基本思想快速排序算法是一种不稳定的排序算法。其时间复杂度为O(nlogn)，最坏复杂度为O(n^2)；快排的平均空间复杂度为O(logn)，关于空间界的

电玩女神/ 2022年08月06日 04:30/ 0 赞/ 148 阅读

相关常见的排序算法——归并排序

归并排序是建立在归并操作上的一种有效的排序[算法][Link 1]。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。　　归并排序 (merg

深碍√TFBOYSˉ_/ 2022年05月17日 10:25/ 0 赞/ 127 阅读

相关常见排序算法思路总结与性能分析

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

拼搏现实的明天。/ 2022年02月05日 04:11/ 0 赞/ 218 阅读

相关常见排序算法

稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。（即原本a在b

墨蓝/ 2022年01月06日 03:01/ 0 赞/ 263 阅读

相关常见的排序算法

冒泡排序思路：需要用n-1个循环，每个循环都从第1个数开始向后遍历，遇到无序的一对数则交换这两个数，第1次遍历完成后，第n个数有序，下次只需要遍历到第n-1个数。以此类

小灰灰/ 2021年11月10日 10:06/ 0 赞/ 291 阅读

相关常见的排序算法

1.直接插入排序我们经常会到这样一类排序问题：把新的数据插入到已经排好的数据列中。将第一个数和第二个数排序，然后构成一个有序序列将第三个数插入进去，构成一个

淩亂°似流年/ 2021年09月18日 11:32/ 0 赞/ 415 阅读

相关选择排序算法和插入排序算法的性能对比

选择排序算法和插入排序算法都是O(n^2)复杂度的算法，但是两者的执行效率还是有较大差距的。 public class Sort { private Sor

r囧r小猫/ 2021年06月24日 15:58/ 0 赞/ 393 阅读