【数据结构】排序：排序算法的分类及各类排序算法对比

Bertha 。 2021-12-10 00:25 495阅读 0赞

\#笔记整理

这几天复习并整理了一下排序算法，发现内容还是挺多的，有些算法和概念很常用也很重要，记录一下。

## 排序 ##

**排序：** 将一组杂乱无章的数据按一定的规律顺次排列起来，使之按关键字递增(或递减)有序排列。  
**排序算法的稳定性（稳定排序，Stable Sort）**：指当数据中存在2个或2个以上键值相等的元素时，这些元素在排序处理前后顺序不变。

由于待排序的记录数量不同，使得排序过程中**涉及的存储器不同**，可将排序方法分为两大类：

*  **内部排序：** 指待排序记录存放在计算机随机存储器中进行的排序过程，即先把待排序的数据放到内存中再进行排序。
 *  **外部排序：** 指待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。

**内部排序** 的方法很多，但就其全面性能而言，很难提出一种被认为是最好的方法，没种方法都有各自的优缺点和适用环境。  
  
  
**内部排序中依据排序策略（原则）进行分类，可大致分为5类：**

*  [插入排序][Link 1]
 *  [交换排序][Link 2]
 *  [选择排序][Link 3]
 *  [归并排序][Link 4]
 *  计数排序

（点击对应的分类可查看分类详解）  
（由于时间原因，部分内容尚未整理完，敬请谅解）

**而内部排序按照工作量（效率）来区分的话，可分为3类：**

*  简单的排序方法，其时间复杂度为 O ( n 2 ) O(n^2) O(n2)；
 *  先进的排序方法，其时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)；
 *  基数排序，其时间复杂度为 O ( d ⋅ n ) O(d·n) O(d⋅n)。

#### 排序方法分类总图 ####

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

#### 各种内部排序方法的性能对比 ####

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

部分内容来源：

1.  《数据结构（C语言版）》----严蔚敏
2.  《数据结构》课堂教学ppt ---- 刘立芳
3.  《数据结构算法与解析（STL版）》 ---- 高一凡
4.  《大话数据结构》 ---- 程杰
5.  《挑战程序设计竞赛2：算法和数据结构》 ---- 渡部有隆

[Link 1]: https://steve.blog.csdn.net/article/details/95931848
[Link 2]: https://steve.blog.csdn.net/article/details/95934166
[Link 3]: https://steve.blog.csdn.net/article/details/95935599
[Link 4]: https://steve.blog.csdn.net/article/details/96337444
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20211209/ffc2c377a5a2416398035e03918f6521.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: /images/20211209/c8ceae3ecfee4ee7a007bf17b62e72b9.png