首先排序（插入、选择、交换）的算法描述如下： 数据元素类型：
typedef struct{ int key;//关键字域 ......//其他域 }ElemType;表的顺序存储结构：
typedef struct{ ElemType r[MAXSIZE+1];//r[0]为监视哨 int length;//表的长度 }SqList;在具体的程序中，我们比较的是关键字，但是我们交换排序的是记录。
插入排序 Insertion Sorting 插入排序的基本思想：每次将一个待排序的记录，按关键字的大小插入到已排好的子序列中的适当位置，直到全部记录插入完毕为止。 （1）直接插入排序 Straight Insertion Sort 稳定的排序方法 时间复杂度：T(n)=O(n^2) 空间复杂度：S(n)=O(1) 直接插入排序代码的思想如下图所示： 完整的程序如下：
#include<stdio.h> #include<iostream> using namespace std; typedef struct{ int key; }ElemType; #define MAXSIZE 20 typedef struct{ ElemType r[MAXSIZE+1]; int length; }SqList; SqList L; void StraightInsertionSort(SqList &L) { int i,j; for(i=2;i<=L.length;i++) { L.r[0]=L.r[i]; for(j=i-1;L.r[j].key>L.r[0].key;j--) { L.r[j+1]=L.r[j]; } L.r[j+1]=L.r[0]; } } int main() { cout<<"请输入顺序表长："<<endl; cin>>L.length; cout<<"请输入顺序表元素："<<endl; for(int i=1;i<=L.length;i++) cin>>L.r[i].key; cout<<"直接插入排序后的序列为："<<endl; StraightInsertionSort(L); for(int j=1;j<=L.length;j++) cout<<L.r[j].key<<" "; }（2）希尔排序 Shell Sort 不稳定的排序方法 排序过程：先取一个正整数d1<n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。 完整程序如下：
#include<stdio.h> #include<iostream> using namespace std; typedef struct{ int key; }ElemType; #define MAXSIZE 20 typedef struct{ ElemType r[MAXSIZE+1]; int length; }SqList; SqList L; void ShellSort(SqList &L,int dk) { int i,j; for(i=dk+1;i<=L.length;i++) { if(L.r[i].key<L.r[i-dk].key) { L.r[0]=L.r[i]; for(j=i-dk;j>0&&L.r[j].key>L.r[0].key;j-=dk) L.r[j+dk]=L.r[j]; L.r[j+dk]=L.r[0]; } } } void ShellInsert(SqList &L) { int dk,k; cout<<"请输入第一次的增量为："<<endl; cin>>dk; cout<<"请输入每次增量的减少量："<<endl; cin>>k; for(int i=dk;i>0;i-=k) { ShellSort(L,i); } } int main() { cout<<"请输入顺序表的长度："<<endl; cin>>L.length; cout<<"请输入顺序表的元素："<<endl; for(int i=1;i<=L.length;i++) cin>>L.r[i].key; ShellInsert(L); cout<<"希尔排序后的序列为："<<endl; for(int j=1;j<=L.length;j++) cout<<L.r[j].key<<" "; } //49 38 65 97 76 13 27 48 55 4其中
void ShellSort(SqList &L,int dk) { int i,j; for(i=dk+1;i<=L.length;i++) { if(L.r[i].key<L.r[i-dk].key) { L.r[0]=L.r[i]; for(j=i-dk;j>0&&L.r[j].key>L.r[0].key;j-=dk) L.r[j+dk]=L.r[j]; L.r[j+dk]=L.r[0]; } } }ShellSort函数利用的就是直接插入排序的思想 EG： 上述代码用的例子是长度为10的序列：49 38 65 97 76 13 27 48 55 4；第一次的增量设为5，每次增量的减少量设为2，即dk=5、3、1然后结束。 运行结果如下图所示：
