【数据结构与算法之排序与查找】各种排序算法的比较

ゝ一纸荒年。 2024-03-25 16:39 91阅读 0赞

#### 【数据结构与算法之排序与查找】各种排序算法的比较 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之排序与查找】各种排序算法的比较

从时间复杂度和空间复杂度进行比较：

<table> 
 <thead> 
 <tr> 
 <th align="center">排序算法</th> 
 <th align="center">一般情况下的时间复杂度</th> 
 <th align="center">最坏情况下的时间复杂度</th> 
 <th align="center">空间复杂度</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="center">直接插入排序</td> 
 <td align="center"> O ( n 2 ) O(n^2) O(n2)</td> 
 <td align="center"> O ( n 2 ) O(n^2) O(n2)</td> 
 <td align="center"> O ( 1 ) O(1) O(1)</td> 
 </tr> 
 <tr> 
 <td align="center">冒泡排序</td> 
 <td align="center"> O ( n 2 ) O(n^2) O(n2)</td> 
 <td align="center"> O ( n 2 ) O(n^2) O(n2)</td> 
 <td align="center"> O ( 1 ) O(1) O(1)</td> 
 </tr> 
 <tr> 
 <td align="center">简单选择排序</td> 
 <td align="center"> O ( n 2 ) O(n^2) O(n2)</td> 
 <td align="center"> O ( n 2 ) O(n^2) O(n2)</td> 
 <td align="center"> O ( 1 ) O(1) O(1)</td> 
 </tr> 
 <tr> 
 <td align="center">希尔排序</td> 
 <td align="center"> O ( n l o g 2 n ) O(nlog_2^n) O(nlog2n)</td> 
 <td align="center"> O ( n l o g 2 n ) O(nlog_2^n) O(nlog2n)</td> 
 <td align="center"> O ( 1 ) O(1) O(1)</td> 
 </tr> 
 <tr> 
 <td align="center">快速排序</td> 
 <td align="center"> O ( n l o g 2 n ) O(nlog_2^n) O(nlog2n)</td> 
 <td align="center"> O ( n 2 ) O(n^2) O(n2)</td> 
 <td align="center"> O ( l o g 2 n ) O(log_2^n) O(log2n)</td> 
 </tr> 
 <tr> 
 <td align="center">堆排序</td> 
 <td align="center"> O ( n l o g 2 n ) O(nlog_2^n) O(nlog2n)</td> 
 <td align="center"> O ( n l o g 2 n ) O(nlog_2^n) O(nlog2n)</td> 
 <td align="center"> O ( 1 ) O(1) O(1)</td> 
 </tr> 
 </tbody> 
</table>

一般情况下，希尔、快排、堆排的时间复杂度相同，排序速度较快，相对而言快排是最快的(只要不是最坏情况)，而堆排序的空间消耗最小。

直接插入排序和冒泡排序的排序速度较慢，如果待排序列最开始就是基本有序或局部有序的，那么使用这两种排序算法会取得满意的效果。在最好情况下( 原序列按值有序)，使用直接插入排序和冒泡排序的时间复杂度为  O ( n ) O(n) O(n)

从待排序列的规模看，序列中元素越少，采用冒泡、直接插入或简单选择就越合适。

当序列的规模较大时，采用希尔、快排或堆排比较合适。

从算法的实现角度看，直接插入排序、简单选择排序和冒泡排序实现起来简单直接，其他的排序算法都可以看作是对这三种算法的改进和提高，实现起来相对复杂。

【排序稳定性】

*  如果序列中相等的元素经过某种算法排序后，仍能保持它们排序前在序列中的相对顺序，则这种排序算法是稳定的。
 *  反之是不稳定的

从算法的稳定性看，直接插入、冒泡是稳定排序算法。简单选择、希尔、快排、堆排都是不稳定的。