1、排序：排序是按关键字的非递减或非递减顺序对一组记录重新进行排列的操作。
2、稳定性：
在序列中若有Ri=Rj（Ri领先于Rj），排序后序列中Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳定的。
3、内部排序：待排序记录全部存放在计算机内存中进行排序的过程。
外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
4、内部排序方法的分类：
插入类：主要包括直接插入排序、折半插入排序和希尔排序。
交换类：主要包括冒泡排序和快速排序。
选择类：主要包括简单选择排序、树形选择排序和堆排序。
归并类：最常见的是2-路归并排序。
分配类：利用分配和收集两种基本操作来完成，主要包括基数排序。
5、存储方式：顺序表、链表。
1、直接插入排序
将一条记录插入到已排好序的有序表中，从而得到一个新的、记录数量增1的有序表。
稳定性：稳定排序。循环条件r[0].key < r[j].key保证的。
适用于顺序表和链式表
2、折半插入法
利用“查找”中的“折半查找”来实现插入排序
稳定性：稳定排序。
只能用顺序表，不能用链式表
适合初始记录无序，n比较大时的情况。
3、希尔排序（缩小增量排序法）
思想：把待排序序列分成若干较小的子序列，然后逐个使用直接插入排序法排序，最后再对一个较为有序的序列进行一次排序，主要是为了减少移动的次数，提高效率。原理应该就是从无序到渐渐有序，要比直接从无序到有序移动的次数会少一些。
稳定性：不稳定排序。{2,4,1,2}，2和1一组4和2一组，进行希尔排序，第一个2和最后一个2会发生位置上的变化。
只能用顺序结构，不能用链式结构
交换排序基本思想：凉凉比较待排序记录的关键字，一旦发现两个记录不满足次序要求时则进行交换，直到整个序列全部满足要求为止。
1、冒泡排序
最简单的交换排序方法。它通过两两比较相邻记录的关键字，如果发生逆序，则进行交换。
可用顺序结构，也可用链式结构
稳定性：稳定排序
2、快速排序
是冒泡排序的改进版。一次交换可能消除多个逆序。
空间复杂度：最好：O(log2n)，最坏：O(n)
稳定性：非顺次的移动导致排序方法是不稳定的。
排序过程中需要定位表的下界和上界，所以适合用于顺序结构，很难用于链式结构。
适合记录无序，n比较大时的情况
1、简单选择排序（直接选择排序）
稳定性：不稳定
2、树形选择排序（锦标赛排序）
对n个记录的关键字进行两两比较，然后在其中n/2（向下取值）个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。
稳定性：稳定排序
3、堆排序
是一种树形选择排序，在排序过程中，将待排序的记录r[1...n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序的序列中选择关键字最大（或最小）的记录。
稳定性：不是稳定排序
只能用于顺序结构，不能用于链式结构
初建堆所需的比较次数比较多，因此记录数较少是不宜采用
将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为2-路归并，2-路归并最为简单和常用。
基本思想：假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2（向下取值）个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止。
稳定性：稳定排序
可用顺序结构，也可用于链式结构，且不需要附加存储空间，但递归实现时仍需要开辟相应的递归工作栈。