1.直接插入排序
//直接插入排序
void InsertSort(ElemType A[], int n){
int i,j;
for(i=2;i<=n;i++) //依次将A[2]~A[n]插入到前面已排序列
if(A[i].key<A[i-1].key){ //若A[i]的关键码小于其前驱,将A[i]插入有序表
A[0]=A[i]; //复制为哨兵,A[0]不存放元素
for(j=i-1;A[0].key<A[j].key;--j) //从后向前查找待插入位置
A[j+1]=A[j]; //向后挪位
A[j+1]=A[0]; //复制到插入位置
}
}
2.折半插入排序
折半插入排序先折半查找出元素的待插入位置,然后统一地移动待插入位置之后的所有元素。
//折半插入排序 void InsertSort(ElemType A[], int n) {
int i,j,low,high,mid;
for(i=2;i<n;i++){ //依次将A[2]~A[n]插入到前面的已排序序列
A[0]=A[i]; //将A[i]暂存到A[0]中
low=1;high=i-1; //设置折半查找范围
while(low<=high){ //折半查找
mid=(high+low); //取中间点
if(A[mid].key>A[0]) high=mid-1; //查找左子树
else low=mid+1; //查找右子树
}
for(j=i_1;j>=high+1;--i)
A[j=1]=A[j]; //后移元素,空出插入位置
A[high+1]=A[0]; //插入操作
} }
3.希尔排序
希尔排序的基本思想:先将待排序表分割成若干形如L[i,i+d,i+2d,…i+kd]的特殊子表,分别进行直接插入排序,当整个表中的元素已呈基本有序时,在对全体记录进行一次直接插入排序。
//希尔排序
void ShellSort(ElemType A[], int n) {
for(dk=n/2;dk>=1;dk=dk/2) //步长变化
for(i=dk+1;i<=n;++i)
if(A[i].key<A[i-dk].key){ //需将A[i]插入有序增量子表
A[0]=A[i]; //暂存在A[0]中
for(j=i-dk;j>0&&A[0].key<A[j].key;j-=dk)
A[j+dk]=A[dk]; //记录后移,查找插入位置
A[j+dk]=A[0]; //插入操作
}
}
希尔排序是不稳定的排序方法,且希尔排序算法仅适用于线性表为顺序存储的情况。