简介：插入排序基本有两步，先是通过比较，得到插入位置，随后移动给需要插入的位置处腾空，最后进行值的插入。

目录

一、直接插入排序

1.1简介：

1.2代码

二、折半插入排序

2.1简介：

2.2代码：

三、希尔排序

3.1简介：

3.2.代码：

四、总代码

一、直接插入排序

1.1简介：

        直接插入排序，主要两步，先找到需要插入的位置，随后进行移动，给位置腾空，最后赋值。其主要思想都在注释里，

        直接插入排序适合：顺序存储和链式存储

        稳定性：稳定，因为是根据位置直接插入的，所以前后位置不会变。（口令：稳稳的幸福，鸡毛插龟壳-（基数排序，冒泡排序，直接插入和折半插入，归并排序））

        时间复杂度：最好的情况为O(n),已经排好序列了，最坏情况为O(),从头到尾每一个数都需要移动判断，

        空间复杂度：O(1)

1.2代码

void InsertSort(int *a,int n)
{//传进数组和实际数据个数 int i,j;for(i=2;i<=n;++i){//查找实际需要插入的位置i if(a[i]<a[i-1])//因为按照递增顺序排，因此发现后面比前面小的情况就需要排序否则跳过，换下一个数据判断 {a[0]=a[i];//哨兵处放实际需要排的值，方便后面比较 for(j=i-1;a[j]>a[0];--j)//因为需要插入数据进行排序，因此需要从后往前后移，给插入的位置腾空移位置 {//给需要存放位置前的位置处，往后移动，腾空位置，当j所指的数据小于等于哨兵时，给哨兵处的值放在j+1位置处即可 a[j+1]=a[j];}//给数据插进腾空的地方。 a[j+1]=a[0];}}
}

二、折半插入排序

2.1简介：

        折半插入是对直接插入的优化，减少了关键字对比的次数，但时间复杂度和空间复杂度和一直插入一样，移动次数没有改变，仅仅减少比较次数，比较次数取决于表中元素n。

        折半插入排序思想是，从第二个元素开始折半查找进行判断，找到该元素需要插入的位置，随后，进行折半查找，最后折半查找结束后low和high紧挨着互换左右位置，low处为需要插入的位置，随后进行移动，把low处及其后面的都往后移动，最后给a[low]=a[0]，赋值即可。

2.2代码：

void InsertHalfSort(int *a,int n)
{int i,j,low,high,mid;//对数组进行排序，先用折半法，查找位置 for(i=2;i<=n;i++){a[0]=a[i];//从第二个数据开始判断比较 low=1;high=i-1;while(low<=high)//查找区间，最后查找完成后low和high左右挨着互换，high+1即low位置处为需要插入的地方 {mid=(low+high)/2;if(a[mid]<a[0])low=mid+1;elsehigh=mid-1;}//折半后，此时low及其之后的数据都是比high处大的，而low位置处为需要插入的地方，因此需要给low机器后面的地方进行后移，给low处数据弄空 for(j=i-1;j>=low;--j){a[j+1]=a[j];}a[low]=a[0];}
}

三、希尔排序

3.1简介：

        希尔不同于直接插入和折半，而是给表分割成无数子表，一趟一趟分割，合并，每一次分割的子表之间进行判断，以及排序移动，最后一趟趟汇总。每趟子表下标为i,i+d

空间复杂度仍未O(1)

时间复杂度为O(),坏的情况下是O()

稳定性：不稳定

适用性：仅适合于顺序存储。需要随机访问支持才行。

3.2.代码：

void ShellSort(int *a,int n)
{int i,j,d;//d为每次增量，随后d每次/2 for(d=n/2;d>=1;d=d/2) //d增量的趟次 {//开始比较， 从第一趟中，第一个比较队中来说，都是从比较队中第二个数据开始与前面的对比，前面的是i-d for(i=d+1;i<=n;i++)//第一个比较队完成后，i++，进行第二个比较队 {if(a[i]<a[i-d])//按递增比较的话，如果后面的比前面的小，那么异常进行记录和交换 {a[0]=a[i];for(j=i-d; j>=0&&a[j]>a[0] ;j=j-d) //随后从队中第一个数据开始，往后移动，移动到它的下一位j+d处。判断条件为j大于0，且当前的值比移动的值大时，进行数据的后移 {a[j+d]=a[j];	}//移动完毕，进行赋值，此时两两交换完成 a[j+d]=a[0];}				}	}	} 

四、总代码

#include <stdio.h>
//插入排序——直接插入排序
void InsertSort(int *a,int n)
{//传进数组和实际数据个数 int i,j;for(i=2;i<=n;++i){//查找实际需要插入的位置i if(a[i]<a[i-1])//因为按照递增顺序排，因此发现后面比前面小的情况就需要排序否则跳过，换下一个数据判断 {a[0]=a[i];//哨兵处放实际需要排的值，方便后面比较 for(j=i-1;a[j]>a[0];--j)//因为需要插入数据进行排序，因此需要从后往前后移，给插入的位置腾空移位置 {//给需要存放位置前的位置处，往后移动，腾空位置，当j所指的数据小于等于哨兵时，给哨兵处的值放在j+1位置处即可 a[j+1]=a[j];}//给数据插进腾空的地方。 a[j+1]=a[0];}}
}
//插入排序——折半插入
void InsertHalfSort(int *a,int n)
{int i,j,low,high,mid;//对数组进行排序，先用折半法，查找位置 for(i=2;i<=n;i++){a[0]=a[i];//从第二个数据开始判断比较 low=1;high=i-1;while(low<=high)//查找区间，最后查找完成后low和high左右挨着互换，high+1即low位置处为需要插入的地方 {mid=(low+high)/2;if(a[mid]<a[0])low=mid+1;elsehigh=mid-1;}//折半后，此时low及其之后的数据都是比high处大的，而low位置处为需要插入的地方，因此需要给low机器后面的地方进行后移，给low处数据弄空 for(j=i-1;j>=low;--j){a[j+1]=a[j];}a[low]=a[0];}
}
//插入排序——希尔排序：
void ShellSort(int *a,int n)
{int i,j,d;//d为每次增量，随后d每次/2 for(d=n/2;d>=1;d=d/2) //d增量的趟次 {//开始比较， 从第一趟中，第一个比较队中来说，都是从比较队中第二个数据开始与前面的对比，前面的是i-d for(i=d+1;i<=n;i++)//第一个比较队完成后，i++，进行第二个比较队 {if(a[i]<a[i-d])//按递增比较的话，如果后面的比前面的小，那么异常进行记录和交换 {a[0]=a[i];for(j=i-d; j>=0&&a[j]>a[0] ;j=j-d) //随后从队中第一个数据开始，往后移动，移动到它的下一位j+d处。判断条件为j大于0，且当前的值比移动的值大时，进行数据的后移 {a[j+d]=a[j];	}//移动完毕，进行赋值，此时两两交换完成 a[j+d]=a[0];}				}	}	} //打印
void PrintSort(int *a,int n)
{int i;for(i=1;i<=n;i++){printf("%d ",a[i]);	}	printf("\n"); 
} int main()
{int a[9]={0,49,38,65,97,76,13,27};int size=7;printf("开始值\n");PrintSort(a,size);//插入6进去int x;printf("请输入插入的值\n"); scanf("%d",&x); a[size+1]=x; size++;printf("\插入后排序\n");
//	InsertSort(a,size);//直接插入排序 
//	InsertHalfSort(a,size);//折半插入排序 ShellSort(a,size);//希尔排序 PrintSort(a,size);}