排序的基本概念
所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下：
输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。
输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。
（1） 排序的分类
1． 按是否涉及数据的内、外存交换分
内部排序：内部排序(简称内排序)，是带排序纪录存放在计算机内存中，并进行的排序过程。细分又可为：插入排序、选择排序、归并排序和基数排序；
外部排序：指的是带排序纪录的数量很大，以致内存一次不能容纳全部纪录，在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法。
注意：
1) 内排序适用于记录个数不很多的小文件
2) 外排序则适用于记录个数太多，不能一次将其全部记录放人内存的大文件。
2． 按策略划分内部排序方法
可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。
（2） 排序算法的基本操作
大多数排序算法都有两个基本的操作：
(1) 比较两个关键字的大小；
(2) 改变指向记录的指针或移动记录本身。
注意：第(2)种基本操作的实现依赖于待排序记录的存储方式。
（3） 排序算法性能评价
1. 评价排序算法好坏的标准
评价排序算法好坏的标准主要有两条：
1) 执行时间和所需的辅助空间
2) 算法本身的复杂程度
2. 排序算法的空间复杂度
若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O(1)，则称之为就地排序(In-PlaceSou)。非就地排序一般要求的辅助空间为O(n)。
3. 排序算法的时间开销
大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。
l 插入排序
一) 直接插入排序
定义：直接插入排序（ straight insertion sort ）是一种最简单的排序方法。它的基本操作是将一个记录插入到一个长度为 m （假设）的有序表中，使之仍保持有序，从而得到一个新的长度为m＋1的有序表。
算法思路：设有一组关键字｛ K 1 ， K 2 ，…， K n ｝；排序开始就认为 K 1 是一个有序序列；让 K 2 插入上述表长为 1 的有序序列，使之成为一个表长为 2 的有序序列；然后让 K 3 插入上述表长为 2 的有序序列，使之成为一个表长为 3 的有序序列；依次类推，最后让 K n 插入上述表长为 n-1 的有序序列，得一个表长为 n 的有序序列。
算法时间复杂度：此算法外循环 n-1 次，在一般情况下内循环平均比较次数的数量级为Ｏ(n) ，所以算法总时间复杂度为Ｏ(n2) 。
直接插入排序的稳定性：直接插入排序是稳定的排序方法
具体算法：
/* 比较数据函数模板 */
template<class Type>
typedef bool __stdcall (*PFunCustomCompare)(const Type *Data_1,const Type *Data_2);
template<class Type>
void InsertSort (Type Array[], int n, PFunCustomCompare pfCompare){
int i,j;
for (i=2 ;i<=n; i++){ //工进行n-1趟插入
Array[0] = Array[i]; // Array[0]为监视哨，也可作下边循环结束标志
j = i-1;
while (pfCompare (Array[j], Array[0]){
Array[j+1] = Array[j];
j--;
}
Array [j+1]= Array [0]; //将r[0]即原r[i]记录内容，插到r[j]后一位置
}
} // InsertSort
或者：不需要监视哨
template<class Type>
void __stdcall InsertSort(Type Array[], int Num, PFunCusomCompare pfCompare){
for (int i=1; i<Num; ++i){
Type temp = Array[i];
int j;
for (j=i-1; j>=0 && pfCompare (t, Array[j]); --j){
Array[j+1] = Array[j];
}
Array[j+1] = temp;
}
}
【例】设有一组关键字序列｛55，22，44，11，33｝，这里 n=5，即有5个记录。请将其按由小到大的顺序排序。排序过程如图9.1所示。
第一趟：[55] 22 44 11 33
第二趟：[22 55] 44 11 33
第三趟：[22 44 55] 11 33
第四趟：[11 22 44 55] 33
第五趟：[11 22 33 44 55]
二) 折半插入排序
定义：当直接插入排序进行到某一趟时，对于 r[i].key 来讲，前边 i-1 个记录已经按关键字有序。此时不用直接插入排序的方法，而改为折半查找，找出 r[i].key 应插的位置，然后插入。这种方法就是折半插入排序（ Binary insertion sort ）。
具体算法：
template<class T>
void BinarySort(T r[],int n){
int i,j,l,h,mid;
for (i=2; i<=n; i++){
r[0]=r[i];
l=1;
h=i-1; //认为在r[1]和r[i-1]之间已经有序
while (l<=h) { //对有序表进行折半查找
mid=(l+h)/2;
if(a[0].key<a[mid].key){
h=mid-1;
}else{
l=mid+1;
}
}
//结果在1位置
for(j=i-1;j>=1;j--){
a[j+1]=a[j];
}
a[1]=a[0];
}
} // BinarySort
折半插入排序的时间复杂度：折半插入排序，关键字的比较次数由于采用了折半查找而减少，数量级为Ｏ (nlog 2 n) ，但是元素移动次数仍为Ｏ (n 2 ) 。故折半插入排序时间复杂度仍为Ｏ (n 2 ) 。折半插入排序方法是稳定的。
三) 2-路插入排序
四) 表插入排序
五) 希尔排序
定义：希尔排序（ shell sort ）是 D ．Ｌ．希尔（ D.L.Shell ）提出的“缩小增量”的排序方法。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为 1 ，这样记录移动次数大大减少，提高了排序效率。希尔排序对增量序列的选择没有严格规定。
算法思路：
①. 先取一个正整数 d1(d 1 <;n) ，把全部记录分成 d1个组，所有距离为 d1的倍数的记录看成一组，然后在各组内进行插入排序；
②. 然后取 d2( d2 < d1 ) 。
③. 重复上述分组和排序操作；直到取 di=1(i>=1) ，即所有记录成为一个组为止。一般选