文档介绍：第12章 内排序
排序是数据结构中一种非常重要且最为常用的一种技术，它在计算机的其它领域应用也非常广泛，在对数据进行处理的过程中，对数据进行排序是不可避免的。在元素的查找过程中就涉及了对数据的排序。排序按照内存和外存的使用情况，可分为内排序和外排序。
排序的基本概念
在介绍有关排序的算法之前，先来介绍与排序相关的基本概念。本节主要介绍排序的基本概念及相关概念。
排序：把一个无序的元素序列按照元素的关键字递增或递减排列为有序的序列。
稳定排序和不稳定排序：在排列过程中，如果存在两个关键字相等即ki=kj(1≤i≤n,1≤j≤n,i≠j)，在排序前对应的元素Ei在Ej之前。
排序的基本概念
内排序和外排序：根据排序过程中，所利用的内存储器和外存储器的情况，将排序分为两类：内部排序和外部排序。
内排序的方法有许多，按照排序过程中采用的策略将排序分为几个大类：插入排序、选择排序、交换排序和归并排序。这些排序方法各有优点和不足，在使用时，可根据具体情况选择比较合适的方法。
排序的基本概念
为了方便，本章的排序算法主要采用顺序存储。相应的类型定义描述如下：
#define MaxSize 50
typedef int KeyType;
typedef struct /*数据元素类型定义*/
{
KeyType key;/*关键字*/
}DataType;
typedef struct /*顺序表类型定义*/
{
DataType data[MaxSize];
int length;
}SqList;
插入排序
插入排序的算法思想是：在一个有序的元素序列中，不断地将新元素插入到该已经有序的元素序列中的合适位置，直到所有元素都插入到合适位置则完成排序。本节的主要学习内容包括两种插入排序：直接插入排序、折半插入排序和希尔排序。
直接插入排序
直接插入排序的基本思想是：假设前i-1个元素已经有序，将第i个元素的关键字与前i-1个元素的关键字进行比较，找到合适的位置，将第i个元素插入。按照类似的方法，将剩下的元素依次插入到已经有序的序列中，完成插入排序。
直接插入排序
void InsertSort(SqList *L)
/*直接插入排序*/
{
int i,j;
DataType t;
for(i=1;i<L->length;i++) /*前i个元素已经有序，从第i+1个元素开始与前i个有序的关键字比较*/
{
t=L->data[i+1]; /*取出第i+1个元素，即待排序的元素*/
j=i;
while(j>-1&&<L->data[j].key)/*寻找当前元素的合适位置*/
{
L->data[j+1]=L->data[j];
j--;
}
L->data[j+1]=t; /*将当前元素插入合适的位置*/
}
}
直接插入排序
折半插入排序
由于插入排序算法的基本思想是，将待排序元素插入到已经有序的元素序列的正确位置，因此，在查找正确插入位置时，可以采用折半查找的思想寻找插入位置。将这种插入排序称为折半插入排序。
折半插入排序
void BinInsertSort(SqList *L)
/*折半插入排序*/
{
int i,j,mid,low,high;
DataType t;
for(i=1;i<L->length;i++) /*前i个元素已经有序，从第i+1个元素开始与前i个的有序的关键字比较*/
{
t=L->data[i+1]; /*取出第i+1个元素，即待排序的元素*/
low=1,high=i;
while(low<=high) /*利用折半查找思想寻找当前元素的合适位置*/
{
mid=(low+high)/2;
if(L->data[mid].key>)
high=mid-1;
else
low=mid+1;
}
for(j=i;j>=low;j--) /*移动元素，空出要插入的位置*/
L->data[j+1]=L->data[j];
L->data[low]=t; /*将当前元素插入合适的位置*/
}
}