*排序属于数据的运算
1、定义：将一组杂乱无章的数据按一定规律顺次排列一起，即将无序序列排成一个有序序列的运算。
（如果参加排序的数据结构包含多个数据域，那么排序往往是针对其中某个域而言）
2、排序的应用十分广泛：程序中间接应用（二分查找、最短路径、最小生成树）
3、排序的分类：
按照数据存储介质：内部排序（数据量不大、数据在内存）和外部排序（数据量较大，数据在外存）
*外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂多。
按比较器个数：串行排序（单处理机，同一时刻比较一对元素）和并行排序（多处理机，同一时刻比较多对元素）
按主要操作：比较排序（用比较的方法：插入排序、交换排序、选择排序、归并排序）和基数排序（不比较元素的大小，仅仅根据元素本身的取值确定其有序位置）
按辅助空间：原地排序（辅助空间用量为O（1）的排序方法，所占辅助空间与参加排序的数据量大小无关）和非原地排序（辅助空间用量超过O（1）的排序方法）
按稳定性：稳定排序（能够使任何数值相等的元素，排序以后相对次序不变）和非稳定排序（不是稳定排序的方法）
*排序的稳定性只对结构类型排序有意义
*排序方法是否稳定，并不能衡量一个排序算法的优劣。
按自然性：自然排序（输入数据越有序，排序的速度越快）和非自然排序（不是自然排序的方法）
4、（1）按排序依据原则
插入排序：直接～、折半～、希尔排序
交换排序：冒泡排序、快速排序
选择排序：简单～、堆排序
归并排序：2-路归并排序
基数排序
（2）按排序所需工作量
简单的排序方法：T(n)=O(n^2)
基数排序：T(n)=O(d.n)
先进的排序方法：T(n)=O(nlogn)
5、存储结构——记录序列以顺序表存储
#define MAXSIZE 20
typedef int KeyType; //设关键字为整型量
//定义每个记录（数据元素）的结构
Typedef struct{KeyType key; //关键字InfoType otherinfo; //其他数据项
}RedType;
//定义顺序表的结构
Typedef struct{RedType r[MAXSIZE+1]; //存储顺序表的结构//r[0]一般作哨兵或缓冲区intlength; //顺序表的长度
}SqList;6、插入排序
（1）基本思想：
边插边排序，保证子序列中随时都是排好序的
（2）基本操作：有序插入
-1、在有序序列中插入一个元素，保持序列有序，有序长度不断增加
-2、起初，a[0]是长度为1的子序列，然后逐一将a[1]至a[n-1]插入到有序子序列中
（3）有序插入方法
-1、在插入a[i]前，数组a的前半段a[0]-a[i-1]是有序段，后半段是停留于输入次序的“无序段”
-2、插入a[i]使a[0]-a[n-1]有序，也就是要为a[i]找到有序位置j，将a[i]插入在a[j]位置
（4）图示
（5）种类
顺序法定位插入位置——直接插入排序、二分法定位插入位置——二分插入排序、缩小增量多遍插入排序——希尔排序
（6）直接插入排序
*复制插入元素、记录后移，查找插入位置、插入到正确位置
*或者使用“哨兵”
复制为“哨兵”、记录后移查找插入位置，插入到正确位置、插入到正确位置
*算法：
void InsertSort(SqList &L){int i,j;for(i=2;i<=L.length;++i){if(L.r[i].key<L.r[i-1].key){. //若<,需将L.r[I]插入有序子表L.r[0]=L.r[i]; //复制为哨兵for(j=i-1;L.r[0].key<L.r[j].key;--i){