【数据结构】排序算法复杂度 及 稳定性分析 【图文详解】

---

前言

前面给大家讲述了各大排序算法的原理、思路以及实现步骤、代码码源，下面让我们来对比一下各大排序之间的算法复杂度以及稳定性分析优劣，加深我们对于各排序算法的理解，帮助我们以后能更快的在具体场景下选择出最适的排序算法。

---

[ 一 ] 小数据基本排序算法

（1）冒泡排序

【数据结构】冒泡排序 （码源实现）

（2）直接插入排序

【数据结构】插入排序

---

[ 二 ] （由基本排序衍生的用作）处理大数据处理排序

（1）堆排序

【数据结构】堆排序（C代码实现 码源）

（2）希尔排序

【数据结构】希尔排序

---

[ 三 ] 大数据速度排序方法

（1）快速排序

【数据结构】深入浅出理解快速排序背后的原理 以及 版本优化【万字详解】（C语言实现）

（2）归并排序

【数据结构】归并排序 的递归实现与非递归实现

---

[ 四 ] 极致速度的整型数据类型的排序

（1）计数排序

【数据结构】深入浅出讲解计数排序【图文详解，搞懂计数排序这一篇就够了】

---

[ 五 ] 其他排序

（1）基数排序：一位一位比较

（2）桶排序

这两种在这里不过多赘述，因为不如前面的高级排序更好，更加适用

---

一、各排序算法的分析和比较

内排序：内存中排序

外排序：在磁盘中排序 【数据太多，内存放不下，转存磁盘了】

• 磁盘一大特点：
  1. 顺序读 顺序写
  2. 不像内存那样支持下标访问，所以外排序会非常慢

归并排序既可以在内存中排序（内排序），也可以在磁盘中排序（外排序）

二、归并排序 外排序算法思路详解

---

☆三、稳定性 概念讲解

相同的数据排序后，相对位置是否变化

稳定性的意义 及 实际应用：

如考试中，考试排名取前三名，先交卷用时少的，成绩先进入数组
排名中成绩高排优先级更高，若成绩相同时，用时少的优先级更高

或 总分相同的，数学更高的优先级更高。

这经常应用于 结构体排序（ 用结构体指针按某一项去进行比较 ）

---

四、排序算法复杂度 及 稳定性分析

• 直接插入排序 稳 遇到相等的就不再往前移了
• • 归并排序 不稳改稳
    
    
    多为 结构体指针 谈稳定性，计数排序谈稳定性无价值。

---

总结