I Base class of sort al
Insert
Swap
Select
II compare diff al
| 名称 | 时间复杂度 | 空间复杂度 | 适用结构 | 优点 | 缺点 | 备注 |
| 直接插入 |
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] | |
| 堆排序 | ||||||
| 归并排序 | ||||||
| 基数排序 |
备注：
[1] 直接插入排序的本质是寻找当前元素在排序子集中的位置
[2] 折半算法的应用优化了比较次数,使其从$O(n^{2})->O(nlog_{2}n)$
[3] 希尔排序本质是通过选取d，即增量序列将集合划分成子集，而其在划分过程中将同值元素划分到不同子集的过程，导致其不稳定
[4] 冒泡排序本质上每一轮都将序列中的一个元素放到了最中位置（最大/最小），其与插入排序的区别是每一轮结束都必有一个元素在其最终位置
[5] 快速排序基于分治算法，其依靠选取递增序列变量d将序列划分
[6] 选择排序的本质是选取元素序列中最小/最大的元素
[7] 简单选择排序与冒泡排序的区别，冒泡排序是减少了比较次数，而简单选择排序是减少了交换次数。而比较次数与序列初始状态无关。故简单选择的时间复杂度受序列影响较小
III code
IV problem
V expandtion