一、直接插入排序
空间复杂度：O(1)
时间复杂度：O(n^2)
稳定性：稳定
适用性：顺序表和链表
//直接插入排序void InsertSort1(int A[],int n){int i,j,temp;for(i=1;i<n;i++){if(A[i]<A[i-1]){temp=A[i];for(j=i-1;j>=0&&A[j]>temp;j--){A[j+1]=A[j]; //元素右移}A[j+1]=temp;}}}
二、折半插入排序
空间复杂度：O(1)
时间复杂度：O(n^2)
稳定性：稳定
适用性：顺序表
//折半插入排序void InsertSort2(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){mid=(low+high)/2;if(A[mid]>A[0])high=mid-1;elselow=mid+1;}for(j=i-1;j>=low;j--)A[j+1]=A[j];A[j+1]=A[0];}}
三、希尔排序（缩小增量排序）
空间复杂度：O(1)
时间复杂度：O(n^1.3)，最坏O(n^2)
稳定性：不稳定
适用性：顺序表
//希尔排序void ShellSort(int A[],int n){for(d=n/2;d>=1;d=d/2){for(i=d+1;i<=n;i++){if(A[i]<A[i-d]){A[0]=A[i];for(j=i-d;j>0&&A[0]<A[j];j-=d)A[j+d]=A[j];A[j+d]=A[0];}}}}
如果觉得《三种插入排序算法：直接插入排序 折半插入排序 希尔插入排序》对你有帮助，请点赞、收藏，并留下你的观点哦！
