假设含 n 个记录的文件内容为 {R1,R2,...,Rn} ，相应的关键字为 {k1,k2,...,kn} 。经过排序确定一种排列 {Rj1,Rj2,...,Rjn} ，使得它们的关键字满足以下递增（或递减）关系： kj1<=kj2<=...<=kjn（或kj1>=kj2>=...>=kjn） 。
排序方法的稳定与不稳定：
内部排序和外部排序：
方法： 在插入第 i 个记录时， R1,R2,...,Ri-1 已经排好序，这时将 Ri 的关键字 ki 依次与关键字 ki-1,ki-2 等进行比较，从而找到应该插入的位置并将 Ri 插入，插入位置及其后的记录依次向后移动。
直接插入排序 是一种 稳定 的排序方法 ， 时间复杂度为O(n^2)，空间复杂度为O(1)。
方法： 首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换这两个记录的值，然后比较第二个记录和第三个记录的关键字，依此类推，直到第 n-1 个记录和第 n 个记录的关键字比较过为止。上述过程称为第一趟冒泡排序，然后再进行多次冒泡排序，直到冒泡排序过程中没有进行相邻位置的元素交换处理为止。
冒泡排序 是一种 稳定 的排序方法 ， 时间复杂度为O(n^2)，空间复杂度为O(1)。
方法： 通过 n-i (1<=i<=n) 再次关键字之间的比较，从 n-i+1 个记录中选出关键字最小的记录，并和第 i 个记录进行交换，当 i 等于 n 时所有记录有序排列。
简单选择排序 是一种 不稳定 的排序方法 ， 时间复杂度为O(n^2)，空间复杂度为O(1)。
又称为“缩小增量排序”，它是对直接插入排序方法的改进。
方法： 先将整个待排序记录分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。具体做法是：先取一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分成 d1 个组，即将所有距离为 d1 倍数序号的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量 d2 (d2<d1) ，重复上述分组和排序工作，依此类推，直到所取的增量 di=1 (di<di-1<...<dc<d1) ，即所有记录放在同一组进行直接插入排序为止。
希尔排序 是一种 不稳定 的排序方法 ， 时间复杂度为O(n^1.3)，空间复杂度为O(1)。
方法： 附设两个位置指示变量 i 和 j ，它们的初值分别指向序列的第一个记录和最后一个记录。设枢轴记录（通常是第一个记录）的关键字为 pivot ，则首先从 j 所指位置起向前搜索，找到第一个关键字小于 pivot 的记录时将记录向前移到 i 指示的位置，然后从 i 所指位置起向后搜索，找到第一个关键字大于 pivot 的记录时将该记录后移到 j 所指位置，重复该过程直至 i 与 j 相等为止。
快速排序 是一种 不稳定 的排序方法 ， 时间复杂度为O(nlogn)，空间复杂度为O(logn)。
方法： 对一组待排序记录的关键字，首先按堆的定义排成一个序列（即建立初始堆），从而可以输出堆顶的最大关键字（对于大根堆而言），然后将剩余的关键字再调整成新堆，便得到次大的关键字，如此反复，直到全部关键字排成有序序列为止。
堆排序 是一种 不稳定 的排序方法 ， 时间复杂度为O(nlogn)，空间复杂度为O(1)。
方法： 将两个或两个以上的有序文件合并成一个新的有序文件。实现方法是：把一个有 n 个记录的无序文件看成是由 n 个长度为 1 的有序子文件组成的文件，然后进行两两归并，得到 n/2 个长度为 2 或 1 的有序文件，再两两归并，如此重复，直到最后形成包含 n 个记录的有序文件为止。
归并排序 是一种 稳定 的排序方法 ， 时间复杂度为O(nlogn)，空间复杂度为O(n)。
方法： 设立 r 个队列，队列的编号分别为 0、1、2、...、r-1 。首先按最低有效位的值把 n 个关键字分配到这 r 个队列中；然后按照队列编号从小到大将各队列中的关键字依次收集起来；接着再按次低有效位的值把刚收集起来的关键字分配到 r 个队列中。重复上述分配和收集过程，直到按照最高有效位分配和收集。这样就得到一个从小到大有序的关键字序列。
对于 n 个记录，执行一次分配和收集的时间为 O(n+r) 。如果关键字有 d 位，则要执行 d 便。所以总的运算时间为 O(d(n+r)) 。
基数排序 是一种 稳定 的排序方法 ， 时间复杂度为O(d(n+rd))，空间复杂度为O(rd)。
各个排序方法的性能比较：
外部排序是对大型文件的排序，待排序的记录存放在外存。
常用的外部排序方法是归并排序。