排序，即重新排列表中的元素，使表中元素满足按关键字有序的过程
对于待排序表中的两个元素 $R_i$ 和 $R_j$，若排序前后 $R_i$ 和 $R_j$ 的相对位置不变，则称排序算法是稳定的，否则是不稳定的，稳定与不稳定是对算法性质的描述，若待排序表中的元素唯一，则选择排序算法时稳定与否无关紧要
在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类：
- 内部排序：排序期间，元素全部存放在内存中
- 外部排序：排序期间，元素无法全部同时存在于内存中，在排序过程中根据要求不断地在内外存中移动
一般所说的排序，一般都是内部排序，分为五大类：
- 插入排序：每次将待排序记录按关键字大小插入到已排好的子序列中
- 选择排序：第 $i$ 趟在后面的 $n-i+1$ 个元素中选择关键字最小的元素作为有序区的第 $i$ 个元素
- 交换排序：根据序列中两元素关键字的比较结果来对换两记录在序列中的位置
- 归并排序：利用分治策略，两两进行归并，即将两个有序表组合为一个新的有序表
- 基数排序：基于关键字各位的大小进行排序
对于外部排序，通常采用归并排序法
内部排序算法的性能取决于时间复杂度与空间复杂度，时间复杂度取决于比较和移动的次数，按照时间复杂度，可以大体分为两类：
- 非线性时间比较类排序：时间复杂度 $O(nlog_2n)$ ~ $O(n^2)$
- 线性时间非比较类排序：时间复杂度 $O(n)$，典型特点是以时间换空间
常见排序算法的比较如下：
