软考-软件设计师：排序算法介绍、稳定排序、不稳定排序、分类、比较、适用场景 作者：马育民 • 2025-04-15 08:57 • 阅读：10005 # 排序 排序后，使得元素是 **递增** 或 **递减** 的关系 ### 稳定排序 和 不稳定排序 两个元素相同，排序前后，这两个元素的位置不变，就是稳定的；否则就是不稳定的 ### 排序分类 | |基础排序 |升级排序 | | ------------ | ------------ | ------------ | |插入类排序 |直接插入排序 |希尔排序 | |交换类排序 |冒泡排序 |快速排序 | |选择类排序 |直接选择排序 |堆排序 | # 算法比较 [](https://www.malaoshi.top/upload/0/0/1GWwrz95GqR.png) # 算法的选择 在选取排序方法时，需要考虑的因素有： - 待排序的元素个数 - 元素本身的大小，如：`0-99` 就比较小，`1000-9999` 相对较大 - 关键字的分布情况，如：基本有序 - 对排序稳定性的要求 - 语言工具的条件 - 辅助空间的大小 ### 序列的元素 数量较小 可采用： - 直接插入排序 - 简单选择排序 **原因：**数量小，算法简单 ### 记录本身信息量大时 用 `简单选择排序` 方法较好 **原因：**由于 `直接插入排序` 所需的记录移动操作，比 `简单选择排序` 多 ### 序列的元素 基本有序 可采用： - 直接插入排序，算法本身快 - 冒泡排序（因为基本有序，不需要交换位置） ### 序列的元素 数量很大，关键字位数较少时 采用 **基数排序** 较好 **关键字位数较少：**比如 最大元素是 `99`，2位数 **原因：**最大数是 `n` 位数，使用基数排序就需要执行 `n` 趟 ### 序列的元素 数量很多 应采用时间复杂度为 `O(nlog₂n)` 的排序方法： - 快速排序：目前被认为是内部排序中最好的方法，当待排序的关键字为随机分布时，快速排序的平均运行时间最短 - 堆排序：只需要一个辅助空间，并且不会出现在快速排序中可能出现的最快情况。 - 归并排序：`快速排序` 和 `堆排序` 都是 **不稳定** 的排序方法，若要求 **排序稳定**，可选择 `归并排序` 原文出处：http://malaoshi.top/show_1GWwqKkOHdJ.html