各种排序算法时间复杂度

末蓝、 2021-09-20 11:20 339阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td colspan="9"> 各种常用排序算法 </td> 
 </tr> 
 <tr> 
 <td> 类别 </td> 
 <td> 排序方法 </td> 
 <td colspan="3"> 时间复杂度 </td> 
 <td> 空间复杂度 </td> 
 <td> 稳定性 </td> 
 <td> 复杂性 </td> 
 <td> 特点 </td> 
 </tr> 
 <tr> 
 <td> 最好 </td> 
 <td> 平均 </td> 
 <td> 最坏 </td> 
 <td> 辅助存储 </td> 
 <td> &nbsp; </td> 
 <td> 简单 </td> 
 <td> &nbsp; </td> 
 </tr> 
 <tr> 
 <td> 插入 排序 </td> 
 <td> 直接插入 </td> 
 <td> O(N) </td> 
 <td> O(N2) </td> 
 <td> O(N2) </td> 
 <td> O(1) </td> 
 <td> 稳定 </td> 
 <td> 简单&nbsp; </td> 
 <td> &nbsp; </td> 
 </tr> 
 <tr> 
 <td> 希尔排序 </td> 
 <td> O(N) </td> 
 <td> O(N1.3) </td> 
 <td> O(N2) </td> 
 <td> O(1) </td> 
 <td> 不稳定 </td> 
 <td> 复杂 </td> 
 <td> &nbsp; </td> 
 </tr> 
 <tr> 
 <td> 选择 排序 </td> 
 <td> 直接选择 </td> 
 <td> O(N) </td> 
 <td> O(N2) </td> 
 <td> O(N2) </td> 
 <td> O(1) </td> 
 <td> 不稳定 </td> 
 <td> &nbsp; </td> 
 <td> &nbsp; </td> 
 </tr> 
 <tr> 
 <td> 堆排序 </td> 
 <td> O(N*log2N) </td> 
 <td> O(N*log2N) </td> 
 <td> O(N*log2N) </td> 
 <td> O(1) </td> 
 <td> 不稳定 </td> 
 <td> 复杂 </td> 
 <td> &nbsp; </td> 
 </tr> 
 <tr> 
 <td> 交换 排序 </td> 
 <td> 冒泡排序 </td> 
 <td> O(N) </td> 
 <td> O(N2) </td> 
 <td> O(N2) </td> 
 <td> O(1) </td> 
 <td> 稳定 </td> 
 <td> 简单 </td> 
 <td> 1、冒泡排序是一种用时间换空间的排序方法，n小时好 2、最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序，最差时间复杂度O(N^2)只是表示其操作次数的数量级 3、最好的情况是数据本来就有序，复杂度为O(n) </td> 
 </tr> 
 <tr> 
 <td> 快速排序 </td> 
 <td> O(N*log2N) </td> 
 <td> O(N*log2N)&nbsp; </td> 
 <td> O(N2) </td> 
 <td> O(1)&nbsp; </td> 
 <td> 稳定 </td> 
 <td> 复杂 </td> 
 <td> 1、n大时好，快速排序比较占用内存，内存随n的增大而增大，但却是效率高不稳定的排序算法。 2、划分之后一边是一个，一边是n-1个， 这种极端情况的时间复杂度就是O(N^2) 3、最好的情况是每次都能均匀的划分序列，O(N*log2N) </td> 
 </tr> 
 <tr> 
 <td colspan="2"> 归并排序 </td> 
 <td> O(N*log2N)&nbsp; </td> 
 <td> O(N*log2N)&nbsp; </td> 
 <td> O(N*log2N)&nbsp; </td> 
 <td> O(n) </td> 
 <td> 稳定 </td> 
 <td> 复杂 </td> 
 <td> 1、n大时好，归并比较占用内存，内存随n的增大而增大，但却是效率高且稳定的排序算法。 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> 基数排序 </td> 
 <td> O(d(r+n)) </td> 
 <td> O(d(r+n)) </td> 
 <td> O(d(r+n)) </td> 
 <td> O(rd+n) </td> 
 <td> 稳定 </td> 
 <td> 复杂 </td> 
 <td> &nbsp; </td> 
 </tr> 
 <tr> 
 <td colspan="9"> 注：r代表关键字基数，d代表长度，n代表关键字个数 </td> 
 </tr> 
 </tbody> 
</table>

注：

1、归并排序每次递归都要用到一个辅助表，长度与待排序的表长度相同，虽然递归次数是O(log2n)，但每次递归都会释放掉所占的辅助空间，

2、快速排序空间复杂度只是在通常情况下才为O(log2n)，如果是最坏情况的话，很显然就要O(n)的空间了。当然，可以通过随机化选择pivot来将空间复杂度降低到O(log2n)。