- 排序：将一组杂乱无章的数据按照一定规律顺次排列
- 数据表：待排序数据元素的有限集合
- 排序算法的稳定性：数据表中两个相同的值在经过算法排序后的相对位置是否改变
- 内排序：排序期间数据元素全部在内存中
- 外排序：数据太多，只能部分在内存中进行，需要不断进行内外存的数据转移
- 排序的时间开销：衡量算法好坏的标志，主要表现是数据比较次数和数据移动次数
- 总关键字比较次数：KCN
- 元素移动次数：RMN
- 插入排序：每步将一个待排序的元素按照其关键字的大小，插入到前面已经排好序的一组元素的适当位置上面，直到全部元素插入完毕为止
- 直接插入排序：从unsorted的列表中找到最大的和sorted列表中最后一个元素交换
- 折半插入排序：利用折半查找算法，找到合适的位置层层递进插入（类似二叉查找树），实际复杂度取决于数据表的初始排列
- 2-路插入排序：复制一个新的数据表，遍历原数据表时判断与新数据表的关系选择插入位置
- 表插入排序：使用链表实现直接插入排序
- 希尔排序：(缩小增量排序)按照一个k的维度进行排序，开始时k值较大，子序列中元素较少，速度快；后来基本已完成排序，需要移动的元素减少，速度仍然很快
- 冒泡排序：两两比较，逆序交换
- 快速排序：任取待排序数据表中的某个元素作为枢轴，按照该元素关键字大小，将整个元素序列划分为左右两个子序列（左侧小于等于、右侧大于），分别对两个子序列重复以上操作。
- 按照快排的递归树的路径，快排的趟数等于树的高度。
- 选择排序：每一趟在后面n-i个待排序元素中选出关键字最小的元素，作为有序元素序列中的第i个元素，待到第n-2趟运行完，待排序元素只剩一个，结束排序
- 直接选择排序：在一组元素V[i]-V[n]中选择有最小关键字的元素；如果不是第一个，则与第一个对调；在剩下的V[i+1]-V[n]中继续执行。
- 树型选择排序：对直接选择排序进行改进，减少关键字比较次数；对n个记录的关键字两两比较，选取n/2个最小者；再将n/2个数字进行两两比较，找出n/4个最小者，直到只剩一个关键字为止
- 堆排序（弥补树型选择排序的不足）：
- 构建大（小）根堆：满足树的任一非叶子节点的关键字均不大（小）于其左右孩子结点的关键字
- 调整堆：比较根结点和其左右孩子的关键字的值
- 归并排序：将两个或两个以上的有序表合并成一个新的有序表（稳定算法）
- 两路归并：先排序两个一组的元素组，再合并两个元素组，一直到只剩一个元素组为止
- 基数排序：
- 多关键字排序的方法
| 排序方法 | 比较次数 | 移动次数 | 稳定性 | 附加存储 |
|---|---|---|---|---|
| 直接插入排序 | n~n2 | 0~n2 | 稳定 | 1 |
| 折半插入排序 | n log2n | 0~n2 | 稳定 | 1 |
| 起泡排序 | n~n2 | 0~n2 | 稳定 | 1 |
| 快速排序 | n log2n~n2 | log2n~n | 不稳定 | log2n~n |
| 简单选择排序 | n2 | 0~n | 不稳定 | 1 |
| 树型选择排序 | n log2n | n log2n | 稳定 | n |
| 堆排序 | n log2n | n log2n | 不稳定 | 1 |
| 归并排序 | n log2n | n log2n | 稳定 | n |