1.假设Ri=Rj,若排序前的序列中Ri领先于Rj,排序后Ri仍领先于Rj，则称所用的排序方法是稳定的，否则称所用的排序方法是不稳定的。
由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，将排序方法分为两大类:
1.内部排序:指待排序记录存放在计算机随机存储器中进行的排序过程。
2.外部排序:待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
2.插入排序
2.其他插入排序
2-路插入排序是在折半插入排序的基础上再改进的，目的是减少排序过程中移动记录的次数，但需要n个记录的辅助空间。
希望在排序过程中不移动记录，只有改变存储结构，进行表插入排序。
3.希尔排序
其基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行一次直接插入排序。
4.快速排序
快速排序是对起泡排序的一种改进，基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，
则可分别对这两部分记录继续进行排序，以达到整个序列有序。
5.选择排序
选择排序的基本思想是:每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列中第i个记录。
1.简单选择排序
2.树形选择排序
又称锦标赛排序,首先对n个记录的关键字进行两两比较,然后在[n/2]个较小者之间再进行两两比较，如此重复直至选出最小关键字的记录为止，整个过程可用
一棵有n个叶子结点的完全二叉树表示。
3.堆排序
堆排序只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间。
堆的定义:n个元素三苏的序列{k1,k2,k3,....,kn}当且仅当满足以下关系时，称之为堆:
k(i) <= k(2i) && k <= k(2i+1)
6.归并排序
归并的含义:将两个或两个以上的有序表组合成一个新的有序表。
2路归并排序:
7.基数排序
基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。
多关键字的排序:最高位优先法(MSD法)和最低位优先法(LSD法)。
链式基数排序:基数排序是借助"分配"和"收集"两种操作对单逻辑关键字进行排序的一种内部排序方法。
8.各种内部排序方法的比较讨论
简单排序 O(n^2) O(n^2) O(1)
快速排序 O(nlogn) O(n^2) O(logn)
堆排序 O(nlogn) O(nlog) O(1)
归并排序 O(nlogn) O(nlogn) O(n)
基数排序 O(d(n+rd)) O(d(n+rd)) O(rd)
简单排序包括除希尔排序之外的所有插入排序，起泡排序和简单选择排序。