1.直接插入排序
1.1 插入排序(insertion sort)的基本思想：
每次将一个待排序的记录，按其关键字大小插入到前面已经排序好的序列中，直到全部记录插入完成为止.
1.2 基本过程
假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n].从i = 2起直到i = n 为止，依次将R[i]插入当前的有序区R[1..i - 1]中，生成含n个记录的有序区.
1.3 基本方法
将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i - 1, i - 2, ....,1)的关键字比较：
1.若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置
2.若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j + 1即为R[i]
1.4 插入位置
关键字比R[i]的关键字大的记录均已后移，所以j + 1的位置已经腾空，只要将R[i]直接插入到此位置即可完成一趟直接插入排序
时间复杂度
当数组和要求排序的顺序相同时，为o(n)
当数组和要求排序的顺序相反时，为o(n * n)
平均时间复杂度为o(n * n)
空间复杂度
O（1）
稳定排序
完整c代码
//首先实现简单数据结构的直接插入排序—数组
#include<stdio.h>
#include<stdlib.h>
#define SIZE 5
//直接插入排序子函数
void StrInsertionSort(int *iptr,int size)
{
int i=1;
int j;
int temp;//temp为中间变量，用于与前i-1个已排好序的元素比较
for(i=1;i<size;i++)
{
temp=*(iptr+i);//temp为要插入的元素
for(j=i-1;j>=0;j--)//对前i-1个与temp比较
{
if(*(iptr+j)>temp)
{
*(iptr+j+1)=*(iptr+j);
*(iptr+j)=temp;//
}
}
//*(iptr+j+1)=temp;
}
}
//主函数
int main()
{
int arr[SIZE];
int k;
printf("依次输入数组各元素\n");
for(k=0;k<SIZE;k++)
{
scanf("%d",arr+k);
}
printf("输出没有排序的数组各元素：\n");
for(k=0;k<SIZE;k++)
{
printf("%d ",*(arr+k));
}
//对数组进行直接插入排序
StrInsertionSort(arr,SIZE);
printf("\n排序后输出数组各元素：\n");
for(k=0;k<SIZE;k++)
{
printf("%d ",*(arr+k));
}
printf("\n");
}
2. 折半插入排序
2.1折半插入排序的过程：
在一个有序序列中，插入关键字和折半序列的中间关键字进行比较，若小则在关键字左边，若大则在关键字右边。
说明：
折半插入排序只是减少了记录进行比较的次数，记录后移量没变。
//折半插入排序子函数
void zhebanInsertionSort(int *iptr,int size)
{
int i=1;
int j;
int low,high,m;
int temp,mid_temp;
//temp为中间变量，用于与前i-1个已排好序的元素中间值比较
//mid_temp为以排好序的序列中间值
for(i=1;i<size;i++)
{
low=0;
high=i-1;
temp=*(iptr+i);//temp为要插入的元素
while(low<=high)//循环找到要移动的位置下限，high+1
{
m=(low+high)/2;
mid_temp=*(iptr+m);
if(temp>mid_temp)
{
low=m+1;
}
else high=m-1;
}
//移动元素，往后统一挪
for(j=i-1;j>=high+1;j--)//
{
*(iptr+j+1)=*(iptr+j);
*(iptr+j)=temp;//
}
}
}
时间复杂度
当数组和要求排序的顺序相同时，为o(n)
当数组和要求排序的顺序相反时，为o(n * n)
平均时间复杂度为o(n * n)
空间复杂度
O（1）
稳定排序