插入排序
插入排序的三种常见方法：
直接插入排序、折半插入排序、希尔排序。
数据存储结构
因为我们是用的是C语言来实现算法，因此我们需要创建一个结构体，用来存放初始数据。
结构体定义如下：
#define MAX 100
typedef int KeyType;
typedef struct{
KeyType key;
}RecordType;
typedef struct{
RecordType R[MAX+1];
int length;
}OrderList;
示例数据
其中data[0]置为0，用来表示哨兵单元。
直接插入排序
基本思想
当插入第i个记录时，前面的R[1]....R[i-1]已经排好序，这时用R[i]依次与前面的关键字比较，直到找
到合适的位置，随后插入。
代码实现
OrderList InsertSort(OrderList L) //直接插入排序
{
int i,j;
for(i=2;i<=10;i++){
L.R[0] = L.R[i]; //L[0]做哨兵单元,同时也用来存放当前i位置记录大小.
j = i - 1; //从i单元的前一个单元开始比较.
while(L.R[0].key<L.R[j].key){ //升序
L.R[j+1] = L.R[j]; //记录依次后移,其中最前面的记录永远会存在连续的两个.
j = j - 1; //j需要前移继续比较.
}
L.R[j+1] = L.R[0]; //j+1为合适的位置.
}
return L;
}验证
复杂度
时间复杂度为：O()
空间复杂度一直为：O(1)
折半插入排序
基本思想
折半插入排序跟前面的折半查找有同曲异工之妙，其中在查找的时候不再是顺序查找，而是折半查
找，但是在数据移动的过程中，仍然是顺序移动下来。
代码实现
OrderList BinsertSort(OrderList L) //折半插入排序
{
int i,j,low,high,mid;
for(i=2;i<=L.length;i++){
L.R[0] = L.R[i];
low = 1;
high = i - 1; //上界应该为i单元的前一个单元位置
while(low <= high){
mid = (low+high) / 2;
if(L.R[0].key < L.R[mid].key)
high = mid - 1;
else
low = mid + 1;
} //待插入的位置一定是low的位置,
for(j=i-1;j>=low;j--) //i单元前面的所有单元依次后移.
L.R[j+1] = L.R[j];
L.R[low] = L.R[0]; //插入单元
}
return L;
}验证
复杂度
若待排序列为正序，则时间复杂度为：O(N)
若待排序列为逆序，则时间复杂度为：O()
空间复杂度一直为：O(1)
希尔排序
希尔排序又叫做“缩小增量排序”。
基本思想
先将整个记录序列分割成若干个子序列，分别进行直接插入排序，在整个序列中的记录“基本有序”
时，再对全体记录进行一次直接插入排序。
其中，子序列并不是进行简单的分割，而是将某个增量d的记录组成一个子序列，让增量d逐步缩
短，直到d=1为止。
d的选取有很多种方法，这里只简单说明最基本的一种（足以应对绝大多数情景）：
d = [n/2]--------->d = [d/2]
下面我们给出一个例子：
假定有一个数据序列为：{5,9,12,2,8,15}
我们来看看希尔排序的一个完整过程：
1.d = [6/2] = 3
将整个序列分为三个子序列：{5,2}、{9,8}、{12,15}。
对三个子序列分别进行直接插入排序，得到新的三个子序列：
{2,5}、{8,9}、{12,15}
由这三个子序列拼凑成一个新的序列为：
{2,8,12,5,9,15}
2.d = [3/2] = 1
此时d = 1，所以直接对整个序列{2,8,12,5,9,15}进行一次直接插入排序，即可获得最终结果。
代码实现
OrderList ShellSort(OrderList L)
{
int i,j,d;
RecordType tmp;
for(d=L.length/2;d>0;d/=2){ //d为本趟希尔排序的增量
for(i=d+1;i<=L.length;i++){
tmp = L.R[i]; //保存待插入单元
j = i - d; //j是与i间隔为d的前一个单元
while(j>=1&&tmp.key<L.R[j].key){
L.R[j+d] = L.R[j]; //R[j]必须后移d个位置,因为比较单元间相隔d
j = j - d;
}
L.R[j+d] = tmp;
}
}
return L;
}验证
复杂度
时间复杂度为：O()
空间复杂度一直为：O(1)
所有代码
#include<stdio.h>
#define MAX 100
typedef int KeyType;
typedef struct{
KeyType key;
}RecordType;
typedef struct{
RecordType R[MAX+1];
int length;
}OrderList;
OrderList InsertSort(OrderList L) //直接插入排序
{
int i,j;
for(i=2;i<=10;i++){
L.R[0] = L.R[i]; //L[0]做哨兵单元,同时也用来存放当前i位置记录大小.
j = i - 1; //从i单元的前一个单元开始比较.
while(L.R[0].key<L.R[j].key){ //升序
L.R[j+1] = L.R[j]; //记录依次后移,其中最前面的记录永远会存在连续的两个.
j = j - 1; //j需要前移继续比较.
}
L.R[j+1] = L.R[0]; //j+1为合适的位置.
}
return L;
}
OrderList BinsertSort(OrderList L) //折半插入排序
{
int i,j,low,high,mid;
for(i=2;i<=L.length;i++){
L.R[0] = L.R[i];
low = 1;
high = i - 1; //上界应该为i单元的前一个单元位置
while(low <= high){
mid = (low+high) / 2;
if(L.R[0].key < L.R[mid].key)
high = mid - 1;
else
low = mid + 1;
} //待插入的位置一定是low的位置,
for(j=i-1;j>=low;j--) //i单元前面的所有单元依次后移.
L.R[j+1] = L.R[j];
L.R[low] = L.R[0]; //插入单元
}
return L;
}
OrderList ShellSort(OrderList L)
{
int i,j,d;
RecordType tmp;
for(d=L.length/2;d>0;d/=2){ //d为本趟希尔排序的增量
for(i=d+1;i<=L.length;i++){
tmp = L.R[i]; //保存待插入单元
j = i - d; //j是与i间隔为d的前一个单元
while(j>=1&&tmp.key<L.R[j].key){
L.R[j+d] = L.R[j]; //R[j]必须后移d个位置,因为比较单元间相隔d
j = j - d;
}
L.R[j+d] = tmp;
}
}
return L;
}
int main()
{
OrderList sample;
sample.length = 10;
int i,data[11]={0,5,8,4,12,35,6,8,67,64,100};
for(i=1;i<11;i++)
sample.R[i].key = data[i];
sample = ShellSort(sample);
for(i=1;i<11;i++)
printf("%d ",sample.R[i].key);
return 0;
}
