前言
| 时间复杂度：一个算法执行所耗费的时间。 空间复杂度：额外空间 稳定性：如果a原本在b前面，而a=b，排序之后a仍然在b的前面，则称此算法稳定，反之不稳定 |
|---|
| 目录 |
| 基于比较
- 三大基本排序算法
- 冒泡
- 选择
- 插入
- 希尔
- 核心排序
- 归并
- 快速
- 堆排
非基于比较
- 计数排序
- 桶排序
- 基数排序
|
| 说明
| 1、格式约定：总结每个排序使用以下格式
- 算法描述/基本思想
- 动图演示
- 伪码(关键步骤) / 源码
- 复杂度
- 自己的总结/一些联想
2、默认升序即从小到大排列
3、含较多个人主观因素在里面
- 基于个人理解。不是采用官方解释
- （也就是说可能有很多错误！🐷
4、所有图来自网络，侵删
5、完整代码可参考GitHub仓库： /EmilyYoung71415/StructuresandAlgorithms-Code
|
行文粗糙，才疏学浅，如有赐教，感激不尽！
冒泡排序
| 算法描述
- 双重循环，每轮确定一个”该轮最大数”
- 外循环限定——此轮的待排序范围，
- 内循环比较——比较相邻两数，如果顺序错误则交换位置
基本思想：
- 每一轮的内部比较，是两两相邻比较，步长为1，变换的代价也是最低的即1位
|
| —- | —- |
| 动图演示
| 
在线可视化：https://visualgo.net/en/sorting |
| 伪码(关键步骤) | 源码
|
| 复杂度 | 时间复杂度 最优O(n) 最差O(n^2) 平均O(n^2)
空间复杂度 O(1)
稳定性 √ |
| 自己的总结\一些联想
| 相较于其他同样每轮确定一个数的其他算法，冒泡内部的每轮比较相当于各路豪杰体重比拼，”每年”有一次晋升机会，来到你面前和你PK的人一定是前n个中最大的，而每次比较步长为1即相邻两两比较，失败或成功代价都最低
|
冒泡扩展:
选择排序
简单选择排序
| 算法描述：
- 双重循环，内部每轮循环确定一个元素的排序位置
- 外循环限定——此轮的待排序范围，
- 内循环比较——以当前循环数为比较初始值，依次遍历后面的未排序的值与其比较，找到当轮的最小值。
基本思想:
- 每次循环在待排序的数据（右边）中选择最小的元素，排在已排序（左边）的最后——以当前循环的数为分界
|
| —- | —- |
| 动图演示
| 
在线可视化：https://visualgo.net/en/sorting |
| 伪码(关键步骤) | 源码
|
| 复杂度 | 时间复杂度 最优O(n) 最差O(n^2) 平均O(n^2)
- 最好与最坏，比较次数都是(第i趟排序进行n-i次比较)
- 交换：最好时交换0；最差时：初始降序，交换n-1次。
- 综合：O(n^2)
空间 O(1)
稳定 实现可以做到稳定
数据越接近正序，直接插入排序的算法性能越好。 | | 自己的总结\一些联想
| 类似于打扑克理牌的过程
|
插入排序
| 算法描述
- 与选择排序类似，双重循环，每次确定一个数的正确位置
- 以当前节点为分界，左边为已排序的，右边为未排序的
- 每次从未排序里选择第一个元素作为新来值，依次与排序元素比较（从右至于左），找到合适的位置即”入队”
算法思想：
- 插入排序是选择新来元素 调整已排序队列
|
| —- | —- |
| 动图演示
| 
在线可视化：https://visualgo.net/en/sorting |
| 伪码(关键步骤) | 源码
|
| 复杂度 | 时间复杂度 最优O(n) 最差O(n^2) 平均O(n^2)
- 最好：顺序，只比较无移动
- 最坏，逆序；
- 比较次数：
- 记录的移动次数：
- 综合 O(n^2)
空间 O(1)
- 稳定 实现可以做到稳定
* 数据越接近正序，直接插入排序的算法性能越好。 | | 自己的总结\一些联想
| 插入与选择十分类似。同样以双重循环，以当前扫描元素为分界分为未排序和已排序左右两堆。
插入是未排序中选择头兵，插入到已排序中，由于选择的简便性那么插入排序时就需要费力气。
选择排序是重在选择，每次选择的时候是在未排序里找到最小的元素，由此便可直接插入已排序队列末尾。
一个形象的比喻的话就是，插入排序像是梁山好汉排名。论资排辈，来一个小弟就和前辈们依次比武论资。
直接插入>选择排序>冒泡排序（>指略胜于） |
插入排序扩展：
希尔排序
| 希尔排序，也叫递减增量排序
回顾一下插入排序的性质
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
- 插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能(加大步长
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止 |
| —- | —- |
| 动图演示
| 时间复杂度 最优O(n)
不稳定 |
| 自己的总结\一些联想
| 外部是：
- 跨步长分组，思想有点像归并，归并是对半开，逐一分组为2；而希尔是跨越式分组，有种分西瓜和梳子梳头的区别？
而在合并中：
- 归并是左右两个子数组，合并转换为合并相邻有序数组的问题。
- 希尔是最外层循环确定步长，每间隔多少步的为一组，以组与组之间除去第一个元素开始为分界，当前元素为基准依次往前遍历while(index-grap—）组内部进行插入排序
总结:
- 当刚开始元素很无序的时候，步长最大，插入排序的元素个数少，速度很快；
- 当元素基本有序了，步长很小，插入排序对于有序的序列效率很高
|
归并排序
| 算法描述
主要采用分而治之的思想，判断一整块数的排序很难，但是我可以不断拆分得到最后两两的组合。排好序的两个数再依次和另外两个相合并
- 分：将问题拆分为小问题
- 治：将分阶段得到的答案修补在一起
|
| —- | —- |
| 动图演示
|
| 伪码(关键步骤) | 源码 |
- 治：合并相邻子序列为一个有序序列的问题
- 分：不断递归的过程
|
| 复杂度
| 时间复杂度 最优O(NlogN) 最差O(NlogN) 平均O(N*logN)
- 归并排序归并时候需要将序列扫描一遍，耗费O（n）时间，由二叉树深度可知，归并排序需要logn次，总复杂度O(NlogN)
空间 O(N+logN)
- 归并时需要n存储空间存放归并结果，以及递归时深度为logn的栈空间
*稳定 实现可以做到稳定性 |
| 自己的总结\一些联想
| 递归：
- 自己调用自己，只是传入的参数变化，实现了子过程复用了父过程，注意递归出口，而到达递归出口时子过程怎么知道它返回哪行他父的变量等数据呢？===》 系统栈帮我们记录了
递归与快排比较起来，像是逆过程。快排从上往下的过程中完成排序，归并排序在合并的时候完成排序，从下往上 |
归并排序扩展
快速排序
| 算法描述
- 在需要排序的数组中，任选一个元素作为“基准”
- 以该基准作为分界，[小于基准值的数们,基准,大于基准的数们]
- 再对于左右两边的”数们”，不断重复选基准，以基准分界的操作，直至划分区间只剩下一个元素。
关键点：
- 怎么在选定一个基准之后，将数组重组成以基准值为划分的呢？
- 并返回基准归位后的下标，供递归调用
快排为什么快：
- 相比冒泡，每次都是交换都是跳跃式。比较和交换的次数变少
- 设定基准值，每次比较之后只需再次迭代比较以基准为划分的剩下的两半。即基于二分思想
|
| —- | —- |
| 动图演示
| 
以某值为基准划分的过程：
如[0,3,6,7,5,4]的第一次划分，取数组的最右边的元素为基准值（这里是4）
- bounder是小于区间的边界初始为-1，动态记录值。】标识，红色表示i指向
- 】0,6,3,7,5,1,4
- 遍历时如果遇到比基准小的则扩大边界值
- 0<4==》 **0**】,3,6,7,5,1,4
- 3<4==》0,**3**】,6,7,5,1,4
- 如果遇到大的元素，不管，继续向下遍历。
- 6、7、5==》 0,3】,6,7,5,1,4
- 当再次遇到小于4的元素:交换1与边界的下一个元素，并扩大边界
- 1<4==》0,3,1】,7,5,**6**,4
- 扫描到最后时候，也将4以同一方式归位
- 4<=4==》0,3,1,4,5,6,7
总结：
- 只有If(arr[i]<=基准值)==》 arr[i]与边界的下一个值交换，扩大边界。
|
| 伪码(关键步骤) | 源码
| 时间复杂度 最优O(NlogN) 最差O(n^2) 平均O(NlogN)
最优：
- 每次划分的十分均匀，排序n个，则递归logn次，然后获得的基准将数组一分为2，各自还需要T(n/2)，于是不断划分下去
最差：
- 有序序列，每次划分只得到一个比上次划分少一个的子序列，如果用递归画出来就是一颗斜树。
平均：
- 设定基准值取在第k个位置。（1<=k<=n）
- 
==> 数学归纳法证得数量级为O(nlogn)
空间 O(logN)
递归的栈空间使用
稳定 常规实现做不到稳定性 |
| 自己的总结\一些联想
| 快速排序的每一轮处理其实把该轮基准数归位，顺带以该基准值为分界划分元素为左右两堆，所有的元素归位了即排序结束。
快排核心即找基准值，在递归调用过程我们可以脑补形成了一个二叉树 |
快速排序扩展
堆排序
| 堆：堆(完全二叉树)，堆由数组模拟而得
堆分为：大根堆和小根堆，升序排序采用大根堆，降序排序采用小根堆。
已知父节点为i===》左节点：2i+1 右节点:2i+1
已知子节点i===》 父节点: (i-1)/2
堆排序思想：
- 建堆heapInsert：将普通数组初始化为大根堆
- 遍历数组，每个元素与其父节点比较，取大者交换。不断迭代。
- 排查排序heapify：将交换后的堆调整为新堆（即在调整堆的过程中又产生新的堆顶元素）
- 怎么调整的？——当前节点和子节点的最大值比较，大着占据当前节点位置
- 每一次范围为0-size的排查之后，总会确定一个最大的元素即排查后的堆顶元素同时待待排序范围size—；
- 交换堆顶与数组的最后一个数 将堆顶划为”排好序的队列中”
- 当范围缩小为0时， 即排查完毕
|
| —- | —- |
| 动图演示
|
| 伪码(关键步骤) | 源码
|
| 复杂度 | 时间复杂度O(N*logN)，额外空间复杂度O(1)
运行时间只要消耗：初始建堆+重堆时的反复排查上。
- 建堆：O（n）
- 排查：第i次确定堆顶元素的重建堆需要O(logi)，且需要取n-1次。排查需要O（nlogn）
- 综合：O（nlogn）
为什么快？记录的比较和交换是有依据的跳跃式。
但不能做到稳定性 |
| 自己的总结\一些联想
| 关键就是两步：
- heapInsert()—-初始化将普通数组对应为某特定堆
- heapify()—-排查
每轮比较找到最大值的思想有点像冒泡过程，但是他是跳跃的 每轮是 left = 2i+1 而不是left++
*归并与快排与堆排比较：
- 若从空间复杂度来考虑：首选堆排序，其次是快速排序，最后是归并排序。
-
若从稳定性来考虑，应选取归并排序，因为堆排序和快速排序都是不稳定的。
-
若从平均情况下的排序速度考虑，应该选择快速排序。
|
计数排序
| 算法描述
- 如果所有的数是10以内的，然后申请10个桶，遍历到相应数时就在数组的相应下标计数。
- 输出时遍历木桶，如果木桶里没有数则不输出，有数则遍历输出（有可能一个桶里有很多数）
|
| —- | —- |
| 动图演示
| 
在线可视化：https://visualgo.net/en/sorting |
| 伪码(关键步骤) | 源码
|
| 复杂度 | // 最差时间复杂度 —— O(n + k)
// 最优时间复杂度 —— O(n + k)
// 平均时间复杂度 —— O(n + k)
// 所需辅助空间 ——— O(n + k)
// 稳定性 —————- 稳定 |
| 自己的总结\一些联想
| 已知道一个数的范围，依照范围画框，遍历数的时候就把该数丢入属于的范围。
这个思想感觉很像，在一堆书里按照科目分书的过程 |
计数排序扩展
桶排序
| 算法描述
- 桶排序就是强化版本的计数排序
算法思想：
- 每个桶存储 一定范围类的键值，桶与桶之间的排序输出按照简单计数排序输出
- 桶内部的数排序可选择插入排序或其他
|
| —- | —- |
| 动图演示
|
| 复杂度 | 最差时间复杂度 —— O(nlogn)或O(n^2)，只有一个桶，取决于桶内排序方式
最优时间复杂度 —— O(n)，每个元素占一个桶
平均时间复杂度 —— O(n)，保证各个桶内元素个数均匀即可
所需辅助空间 ——— O(n + bn)
稳定性 —————- 稳定 |
| 自己的总结\一些联想
| 计数+其他排序方式。
有点像哈希表解决冲突 |
基数排序
| 算法描述
- 桶排序就是强化版本的计数排序 分配+收集
- 适合更大范围的数
算法思想：
- 将所有待比较正整数统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始进行基数为10的计数排序，一直到最高位计数排序完后，数列就变成一个有序序列（利用了计数排序的稳定性）
|
| —- | —- |
| 动图演示
| 
在线可视化：https://visualgo.net/en/sorting |
| 伪码(关键步骤) | 源码
|
| 复杂度 | // 最差时间复杂度 —— O(n dn)
// 最优时间复杂度 —— O(n dn)
// 平均时间复杂度 —— O(n dn)
// 所需辅助空间 ——— O(n dn)
// 稳定性 —————- 稳定 |
| 自己的总结\一些联想
| 为什么低位开始比较？
- 低位的权值小,先按低位局部排序,再往高位走,又可以以更大的权值来调整
可以用高位比较吗？
- 最后一次排序的时候，所依据的肯定是权值高的。就像比较两个数一样，如果高位大的话，低位就不用看
MSD版的基位排序
- 由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中
- 在进行完最低位数的分配后再合并回单一的数组中
理解：(与扑克牌为例，关键字有花色和数值)
- 花色顺序：梅花<方块<红心<黑桃
面值顺序：2<3<4<...<10
- LSD:先按照面值从大到小分成13堆，小大到小排序，再按照花色顺序排序
==》LSD的基数排序适用于位数少的数列，如果位数多的话，使用MSD的效率会比较好 |
基数排序扩展
总结
各大排序算法的复杂度总结
参考资料
《大话数据结构》
若有收获，就点个赞吧
0 人点赞
