【AL】Sort algorithm
I Base class of sort al
Insert
Swap
Select
II compare diff al[考点I]
| 名称 | 时间复杂度 | 空间复杂度 | 适用结构 | 优点 | 缺点 | 备注 |
| 直接插入 |
O(n)~O(n^2) |
O(1) | 基本有序线性表 | 稳定 | [1] | |
| 折半插入 | O(n)~O(n^2) | O(1) | 基本有序线性表 | 稳定 | [2] | |
| 希尔排序 | O(n^1.3)~O(n^2) | O(1) | 不稳定 | [3] | ||
| 冒泡排序 |
O(n)~O(n^2) |
O(1) | 基本有序线性表 | 稳定 | [4] | |
| 快速排序 | O(nlogn) |
O(logn)~O(n) |
随机线性序列 | 不稳定 | [5] | |
| 简单选择 | O(n^2) | O(1) | 基本有序线性表 | 不稳定 | [6] | |
| 堆排序 | [7] | |||||
| 归并排序 |
O(nlogn) |
O(n ) |
没有区别 | 稳定 | [8] | |
| 基数排序 | O(d(r+n)) | O(r) | 没有区别 | 稳定 | [9] |
备注：
[1] 直接插入排序的本质是寻找当前元素在排序子集中的位置
[2] 折半算法的应用优化了比较次数,使其从$O(n^{2})->O(nlog_{2}n)$
[3] 希尔排序本质是通过选取d，即增量序列将集合划分成子集，而其在划分过程中将同值元素划分到不同子集的过程，导致其不稳定
[4] 冒泡排序本质上每一轮都将序列中的一个元素放到了最中位置（最大/最小），其与插入排序的区别是每一轮结束都必有一个元素在其最终位置
[5] 快速排序需要递归函数栈，故其最坏情况下，空间利用率达到O(n)
[6] 选择排序的本质是选取元素序列中最小/最大的元素
[7] 简单选择排序与冒泡排序的区别，冒泡排序是减少了比较次数，而简单选择排序是减少了交换次数。而比较次数与序列初始状态无关。故简单选择的时间复杂度受序列影响较小
内外部排序算法比较与应用[考点II]
III code
IV problem
1. [2022年统考]二路归并操作的功能是：将两个有序表合并成一个新的有序表
考察了最基本的定义。所以最基本定义不能不认识。
V expandtion
作者：TangBao~
-------------------------------------------
个性签名：啦啦啦~这是个勤快的作者呢~(っ•̀ω•́)っ✎⁾⁾！