排序算法时间复杂度和空间复杂度比较

水深无声 2022-09-29 06:44 234阅读 0赞

## 时间复杂度 ##

n^2表示n的平方,选择排序有时叫做直接选择排序或简单选择排序

<table> 
 <tbody> 
  <tr> 
   <td><strong>排序方法</strong></td> 
   <td><strong>平均时间</strong></td> 
   <td><strong>最好时间</strong></td> 
   <td><strong>最坏时间</strong></td> 
  </tr> 
  <tr> 
   <td>桶排序(不稳定)</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>基数排序(稳定)</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>归并排序(稳定)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
  </tr> 
  <tr> 
   <td>快速排序(不稳定)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(n^2)</td> 
  </tr> 
  <tr> 
   <td>堆排序(不稳定)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
  </tr> 
  <tr> 
   <td>希尔排序(不稳定)</td> 
   <td>O(n^1.25)</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
  </tr> 
  <tr> 
   <td>冒泡排序(稳定)</td> 
   <td>O(n^2)</td> 
   <td>O(n)</td> 
   <td>O(n^2)</td> 
  </tr> 
  <tr> 
   <td>选择排序(不稳定)</td> 
   <td>O(n^2)</td> 
   <td>O(n^2)</td> 
   <td>O(n^2)</td> 
  </tr> 
  <tr> 
   <td>直接插入排序(稳定)</td> 
   <td>O(n^2)</td> 
   <td>O(n)</td> 
   <td>O(n^2)</td> 
  </tr> 
 </tbody> 
</table>

O(n)这样的标志叫做渐近时间复杂度,是个近似值.各种渐近时间复杂度由小到大的顺序如下

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

一般时间复杂度到了2^n(指数阶)及更大的时间复杂度,这样的算法我们基本上不会用了,太不实用了.比如递归实现的汉诺塔问题算法就是O(2^n).

平方阶(n^2)的算法是勉强能用,而nlogn及更小的时间复杂度算法那就是非常高效的算法了啊.

### 空间复杂度 ###

冒泡排序,简单选择排序,堆排序,直接插入排序,希尔排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引)

快速排序空间复杂度为logn(因为递归调用了) ,归并排序空间复杂是O(n),需要一个大小为n的临时数组.

基数排序的空间复杂是O(n),桶排序的空间复杂度不确定

### 最快的排序算法是桶排序 ###

所有排序算法中最快的应该是桶排序(很多人误以为是快速排序,实际上不是.不过实际应用中快速排序用的多)但桶排序一般用的不多,因为有几个比较大的缺陷.

1.待排序的元素不能是负数,小数.

2.空间复杂度不确定,要看待排序元素中最大值是多少.