DSA之常用的排序方法及其时间复杂度总结

柔光的暖阳◎ 2022-05-09 23:00 85阅读 0赞

数据结构与算法（DSA）学习笔记之[排序][Link 1]

*  数据结构中的一种基本运算，分为内(部)排序和外(部)排序两大类。

内排序：待排序的数据量不大，全部数据都可以放入内存，排序操作完全在内存中进行。

外排序：待排序的数据量大，全部数据不能同时放在内存中，需要借助外存完成排序过程。涉及到数据内外存交换的问题，将数据分批读到内存中去排序，然后写入外存中。

常用的排序方法有：

1.  插入排序
    
    1.  [直接插入排序][Link 2]：
    2.  [希尔排序][Link 3]：又称缩小增量排序，是插入排序的一种改进。在两种请况下比较有效：1、当数据序列基本有序时；2、当数据量很少时。基本思想：将一个长的数据段划分为多个短的数据段，然后在每个短的数据段上利用直接插入排序进行排序，最后再将多个有序的短数据段拼接成整段数据段。
    3.  折半插入排序：在进行插入排序时，用折半查找法寻找插入位置，从而排序过程中的比较次数。
2.  交换排序
    
    1.  [冒泡排序][Link 4]：每次从数组最前端开始，逐渐向后扫描，找出本次范围内的最大者放到本范围的最后位置，然后重复这个过程。
    2.  [快速排序][Link 5]：步骤：
        
        1.  从数组中选择一个基准值：1.第一个元素；2.从第一、中间、最后三个元素中随机选一个；3.选接近于中间值的元素。
        2.  遍历整个数组，将所有小于和大于基准值的元素组成两个子数组（无序的）
        3.  对子数组快速排序：利用分而治之思想，调用递归实现子数组排序
3.  选择排序：
    
    1.  [直接选择排序][Link 6]：每次从数组中选择一个最小的元素转移到一个新的有序数组中，递归实现，直至最后一个元素。
    2.  [堆排序][Link 7]：每次将根元素（即堆顶元素）输出，然后重排得到一个新的堆，再输出堆顶元素；重复这个过程，直至堆中所有元素都输出为止。
    3.  树形选择排序
4.  归并排序：将两个或两个以上的有序序列合并为一个有序序列。归并排序就是反复合并有序序列的过程，由最初的数量众多的短顺串，逐步合并为一个包含所有数据的结果顺串。
5.  基数排序

八大排序算法：快速排序、冒泡排序、直接选择排序、堆排序、归并排序、直接插入排序、折半插入排序、希尔排序。

几种内部排序方法的比较：

<table> 
 <tbody> 
 <tr> 
 <td> 排序方法 </td> 
 <td> 最优时间复杂度 </td> 
 <td> 平均时间复杂度 </td> 
 <td> 最差时间复杂度 </td> 
 <td> 稳定性 </td> 
 </tr> 
 <tr> 
 <td> 插入排序 </td> 
 <td> O(n) </td> 
 <td> O(n^2) </td> 
 <td> O(n^2) </td> 
 <td> 稳定 </td> 
 </tr> 
 <tr> 
 <td> 冒泡排序 </td> 
 <td> O(n^2) </td> 
 <td> O(n^2) </td> 
 <td> O(n^2) </td> 
 <td> 稳定 </td> 
 </tr> 
 <tr> 
 <td> 选择排序 </td> 
 <td> O(n^2) </td> 
 <td> O(n^2) </td> 
 <td> O(n^2) </td> 
 <td> 稳定 </td> 
 </tr> 
 <tr> 
 <td> 希尔排序 </td> 
 <td> O(n^(3/2)) </td> 
 <td>&nbsp;</td> 
 <td>&nbsp;</td> 
 <td> 不稳定 </td> 
 </tr> 
 <tr> 
 <td> 快速排序 </td> 
 <td> O(n log n) </td> 
 <td> O(n log n) </td> 
 <td> O(n^2) </td> 
 <td> 不稳定 </td> 
 </tr> 
 <tr> 
 <td> 归并排序 </td> 
 <td> O(n log n) </td> 
 <td> O(n log n) </td> 
 <td> O(n log n) </td> 
 <td> 稳定 </td> 
 </tr> 
 <tr> 
 <td> 堆排序 </td> 
 <td> O(n log n) </td> 
 <td> O(n log n) </td> 
 <td> O(n log n) </td> 
 <td> 不稳定 </td> 
 </tr> 
 <tr> 
 <td> 基数排序 </td> 
 <td> O(n log n) </td> 
 <td> O(n log n) </td> 
 <td> O(n log n) </td> 
 <td> 稳定 </td> 
 </tr> 
 </tbody> 
</table>

大多数情况下，我们用平均时间复杂度来衡量一个排序算法的优劣。

在几种排序算法中，如果考虑平均时间复杂度的话，快速排序算法性能最好，归并排序次之，堆排序最差；特别是当待排序数据量n很大时，归并排序优于堆排序。

有算法理论证明，任何一种内部排序算法所能达到的最佳时间复杂度为O(n log n)。

通常，平均时间复杂度为O(n^2)的排序算法基本上是稳定的。

[Link 1]: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F/1066239?fr=aladdin
[Link 2]: https://baike.baidu.com/item/%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F/8255911
[Link 3]: https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
[Link 4]: https://baike.baidu.com/item/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F
[Link 5]: https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95?fromtitle=%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F&fromid=2084344
[Link 6]: https://baike.baidu.com/item/%E7%9B%B4%E6%8E%A5%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F
[Link 7]: https://baike.baidu.com/item/%E5%A0%86%E6%8E%92%E5%BA%8F