（一）排序的稳定性
若在待排序的一组序列中，M和N关键字相同，且在排序前M领先于N，那么排序后，如果M和N的相对次序保持不变，M仍领先于N，则称此类排序方法为稳定的，反之则称此类排序不稳定。
（二）内部排序和外部排序
内部排序：指待排序记录全部存放在内存中进行排序。
外部排序：指待排序记录数量很大，以至内存不能容纳全部记录，在排序中尚需对外存进行访问。
（三）排序基本操作
（1）比较两个关键字大小。
（2）将记录从一个位置移动到另一个位置。
（四）常见排序算法
算法 | 分类 | 说明 | 稳定性 | 时间复杂度 | 空间复杂度 | |
1 | 简单排序 | 直接插入排序 | 是一种简单的排序方法。 插入前其他元素已排好序，该元素与其他元素逐个比较。 插入成功后，插入位置及其后的元素依次向后移动。 | 稳定 | O(n2) | O(1) |
冒泡排序 | 逐次比较第n个和第n+1个元素，若为逆序则交换，直到全部完成。 | 稳定 | O(n2) | O(1) | ||
简单选择排序 | 在未排序数列中找到最小(or最大)元素，将其存放到数列起始位置，其后操作类似。直到所有元素均排序完毕。 | 不稳定 | O(n2) | O(1) | ||
2 | 希尔排序 | 又称“缩小增量排序”，是对直接插入排序的改进。 先将整个待排元素序列分割成若干子序列，分别进行直接插入排序，待整个序列元素基本有序时，再对全体进行直接插入排序。 | 不稳定 | 约O(n1.25) | O(1) | |
3 | 快速排序 | 在目前内部排序方法中被认为最好。 通过一次排序将待排元素划分为独立的两部分，前半区中元素均不大于后半区，再分别对这两部分元素继续快速排序。 | 不稳定 | O(nlog2n) | O(log2n)- O(n) | |
4 | 堆排序 | 将待排序序列构造成一个大顶堆，最大值就是堆顶根节点。将其与末尾元素交换，末尾就为最大值。然后将剩余元素重新构造成一个堆，会得到n个元素次小值。如此反复执行。 | 不稳定 | O(nlog2n) | O(1) | |
5 | 归并排序 | 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。 | 稳定 | O(nlog2n) | O(n) | |
（五）希尔排序
（六）快速排序
（七）堆排序
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
对堆中的结点按层进行编号，将这种逻辑结构映射到数组中。
（八）归并排序
（九）排序考虑因素
待排序的记录个数，记录本身的大小，关键字的分布情况，对排序稳定性的要求，语言工具的条件，辅助空间的大小等。
条件 | 排序方法 | |
1 | 排序记录数目较小时 | 插入排序和简单选择排序 当记录本身信息量较大时，使用简单选择排序。 |
2 | 排序记录基本有序 | 直接插入排序或冒泡排序 |
3 | n较大 | 快速排序、堆排序或归并排序 |
4 | 待排序随机分布 | 快速排序的平均时间最短 |
5 | 记录本身信息量较大 | 为避免耗费大量时间移动记录，可采用链表作为存储结构。 |
通常可将归并排序和直接插入排序结合起来使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并。
（十）外部排序
外部排序：对大型文件排序，待排序记录存放在外存。在排序过程中，内存只存储文件的部分记录，整个排序过程需要进行多次内外存间的数据交换。
排序方法：归并排序
（1）生成归并段。把文件记录分段读入内存，排序后输出到外存文件；
（2）对第一阶段形成的归并段，一次次进行归并，使有序段逐渐加长，直到完成。