函数分析：InsertSort(SqList &L) 参数：顺序表L 功能：排序（默认升序）空间复杂度：O(1) 时间复杂度：O(n方)
                           稳定性：稳定
 
代码：
 
//直接插入排序 升序排序
void InsertSort(SqList &L)
{
	int temp;int i,j;
	for(int i=2;i<=L.length;i++)
	{
		if(L.data[i]<L.data[i-1])//比较有序表最后一个
		{
		
			L.data[0]=L.data[i];//放入哨兵中
			L.data[i]=L.data[i-1];
			for(j=i-2;L.data[0]<L.data[j];j--)//比较后移
			{
				L.data[j+1]=L.data[j];
			}
			L.data[j+1]=L.data[0];//哨兵入列
		}
	}
	PrintList(L);
}
 
全部代码：
 
/*
    Project: insert_sort(直接插入排序) 
    Date:    2018/12/27
    Author:  Frank Yu
    InsertSort(SqList &L) 参数：顺序表L 功能：排序（默认升序）空间复杂度：O(1) 时间复杂度：O(n方)
	                      稳定性：稳定
	思想:L[0]设置为“哨兵”，当前数据与前一个数据进行比较，若小于，则说明需要插入，将数据放入到哨兵。
	     边比较，边后移，直至找到正确位置，将哨兵插回。
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define MaxSize 100
#define ElemType int
#define Status int
using namespace std;
//顺序表数据结构
typedef struct
{
	ElemType data[MaxSize];//顺序表元素
	int length;            //顺序表当前长度
}SqList;
//***************************基本操作函数*******************************//
//初始化顺序表函数，构造一个空的顺序表 
Status InitList(SqList &L)
{
	memset(L.data,0,sizeof(L));//初始化数据为0
	L.length=0;                //初始化长度为0
	return 0;
}
//创建顺序表函数 初始化前n个数据
bool CreatList(SqList &L,int n)
{
	if(n<0||n>MaxSize)false;//n非法
	for(int i=1;i<n+1;i++)//L[0]作为哨兵
	{
		scanf("%d",&L.data[i]);
		L.length++;
	}
	return true;
}
//插入函数 位置i插入数据 i及之后元素后移  1=<i<=length+1 
bool InsertList(SqList &L,int i,ElemType e)
{
	if(i<1||i>L.length+1) //判断位置是否有效
     {
		printf("位置无效！！！\n");
    	return false;
	 }
	if(L.length+1>=MaxSize)//判断存储空间是否已满
	{
		printf("当前存储空间已满！！！\n");
		return false;
	}
	for(int j=L.length+1;j>=i;j--)//位置i及之后元素后移
	{
		L.data[j]=L.data[j-1];
	}
	L.data[i]=e;
	L.length++;
	return true;
}
//删除函数 删除位置i的元素 i之后的元素依次前移
bool  ListDelete(SqList &L,int i)
{
	if(i<1||i>L.length)//判断位置是否有效
     {
		printf("位置无效！！！\n");
    	return false;
	 }
	for(int j=i+1;j<=L.length;j++)//位置i之后元素依次前移覆盖
	{
		L.data[j-1]=L.data[j];
	}
	L.length--;
	return true;
}
//查找函数 按位置从小到大查找第一个值等于e的元素 并返回位置
int LocateElem(SqList L,ElemType e)
{
 for(int i=1;i<L.length+1;i++)//从低位置查找
	{
		if(L.data[i]==e)
			return i;
	}
 return 0;
}
//********************************功能函数*****************************************//
//输出功能函数 按位置从小到大输出顺序表所有元素
void PrintList(SqList L)
{
	printf("当前顺序表所有元素:");
	for(int i=1;i<L.length+1;i++)
	{
		printf("%d ",L.data[i]);
	}
	printf("\n");
}
//创建顺序表函数
void Create(SqList &L)
{
	int n;bool flag;
	printf("请输入要创建的顺序表长度(>1):");
	scanf("%d",&n);
	printf("请输入%d个数（空格隔开）:",n);
	flag=CreatList(L,n);
	if(flag){
		printf("创建成功！\n");
		PrintList(L);
	}
	else printf("输入长度非法！\n");
}
//插入功能函数 调用InsertList完成顺序表元素插入 调用PrintList函数显示插入成功后的结果
void Insert(SqList &L)
{
  int place;ElemType e;bool flag;
  printf("请输入要插入的位置(从1开始)及元素:\n");
  scanf("%d%d",&place,&e);
  flag=InsertList(L,place,e);
  if(flag) 
  {
	printf("插入成功！！！\n");
	PrintList(L);
  }
}
//删除功能函数 调用ListDelete函数完成顺序表的删除 调用PrintList函数显示插入成功后的结果
void Delete(SqList &L)
{
  int place;bool flag;
  printf("请输入要删除的位置(从1开始):\n");
  scanf("%d",&place);
  flag=ListDelete(L,place);
  if(flag) 
  {
	printf("删除成功！！！\n");
	PrintList(L);
  }
}
//查找功能函数 调用LocateElem查找元素
void Search(SqList L)
{
  ElemType e;int flag;
  printf("请输入要查找的值:\n");
  scanf("%d",&e);
  flag=LocateElem(L,e);
  if(flag) 
  {
	printf("该元素位置为:%d\n",flag);
  }
  else
	  printf("未找到该元素！\n");
}
//直接插入排序 升序排序
void InsertSort(SqList &L)
{
	int temp;int i,j;
	for(int i=2;i<=L.length;i++)
	{
		if(L.data[i]<L.data[i-1])//比较有序表最后一个
		{
		
			L.data[0]=L.data[i];//放入哨兵中
			L.data[i]=L.data[i-1];
			for(j=i-2;L.data[0]<L.data[j];j--)//比较后移
			{
				L.data[j+1]=L.data[j];
			}
			L.data[j+1]=L.data[0];//哨兵入列
		}
	}
	PrintList(L);
}
//菜单
void menu()
{  
   printf("********1.创建            2.插入*********\n");
   printf("********3.删除            4.查找*********\n");
   printf("********5.直接插入排序    6.输出*********\n");
   printf("********7.退出\n");
}
int main()
{
 SqList L;int choice;
 InitList(L);
 while(1)
 {
  menu();
  printf("请输入菜单序号：\n");
  scanf("%d",&choice);
  if(7==choice) break;
  switch(choice)
  {
  case 1:Create(L);break;
  case 2:Insert(L);break;
  case 3:Delete(L);break;
  case 4:Search(L);break;
  case 5:InsertSort(L);break;
  case 6:PrintList(L);break;
  default:printf("输入错误！！！\n");
  }
 }
 return 0;
}
 
结果截图：
 
 
 

  
  
 
 
更多数据结构实现：数据结构严蔚敏版的实现（含全部代码）
 
有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。

数据结构——C语言实现直接插入排序算法
 
一、基本思想
        直接插入排序算法是在一个已经有序的记录上，将下一个待排序的数，有序的插入已排好序的记录中，这个过程一直持续到将所有待排数全部插入到有序记录中才停止。
 例如，如果将一组数：      2      5      3      7      4      3*
 用直接插入排序算法实现从小到大的排序，那么其过程如下所示：
 （2）    5        3      7      4      3*
 （2        5）    3      7      4      3*
 （2       3         5）  7      4       3*
 （2        3        5      7）  4       3*
 （2        3        4      5      7）    3*
 （2        3        3*     4     5       7）
        由上述过程我们可以看到两个3在比较时后面一个3*在排序之后仍然处于后面的位置，这就体现出了直接插入排序算法的稳定性。
 二、C语言算法实现
 
#include<stdio.h>
void InsertSort(int a[],int length)  //从小到大排序
{
	int i,j,temp;
	for(i=1;i<length;i++)//从数组的第二个值开始插入
	{
		if(a[i]<a[i-1])  //若第i位小于第i-1位
		{
			temp=a[i];  //将第i位暂放入temp中，这时可以想象为第i位为空
			a[i]=a[i-1];  //将第i-1位后移一位到第i位中，这时可想象为第i-1位为空
			for(j=i-2;a[j]>temp;j--)  //继续将temp中的值和第i-2位比较
			{
				a[j+1]=a[j];  //若第i-2位大于temp，则将第i-2位后移到第i-1位中
			}
				a[j+1]=temp;  //循环至第j位小于等于temp值时，则将temp值放在第j+1位中
		}
	}
}
int main()
{
	int i;
	int r[6]={2,5,3,7,4,3};
	InsertSort(r,6);
	for(i=0;i<6;i++) //循环输出
		printf("%d",r[i]);
}
 
运行结果为
 
       接下来我们来分析直接插入排序算法的复杂度：
        空间复杂度：在这个算法中所占用的额外空间只有temp，temp用来暂时存放待插入的数，所以空间复杂度为S(n)=O(1)。
        时间复杂度：执行算法的时间耗费主要取决于数据的分布情况，最好的情况是所有记录是顺序，最坏情况是逆序。若待排序记录是随机的，则时间复杂度T(n)=O(n²)
        从算法的基本思想来看，直接插入排序算法简便且比较适用于记录数目少且基本有序的情况，当待排序数目较大时，其性能就不好。

                                   数据结构常见的八大排序算法之直接插入排序
 
 一、简述
 
        直接插入排序是一种最简单的排序算法，直接插入的算法基本思想是：仅有一个元素的序列总是有序的，因此，对n个记录的序列，可从第二个元素开始直接到第n个元素，逐个向有序序列中执行插入操作，从而得到n个元素按关键字有序的序列。一般来说，在含有j-1个元素的有序序列中插入一个元素的方法是：从第j-1个元素开始依次向前搜索应当插入的位置，并且在搜索插入位置的同时可以后移元素，这样当找到适当的位置时，即可插入元素。原理简述：顺序把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。
 
二、步骤展示
 
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
 
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5
 
三、时空复杂度
 
最好的情况下，即待排序序列按关键字已经有序排列，每趟操作只需1次或者0次移动
 
在最坏的情况下，即待排序序列按关键字逆排序序列，这时在第j趟操作中，为插入元素需要同前面的j个元素进行j次关键字比较，移动元素的次数为j+1次。此时有：总比较次数=n(n-1)/2次，总移动次数 = （n+2)(n-1)/2次
 
平均情况下：即在第j趟操作中，插入记录大约需要时间同前面的j/2个元素进行关键字比较，移动记录次数j/2+1次
 
直接插入排序的时间复杂度：O（n2）
 
空间复杂度：O(1)，没有分配内存。
 
四、代码示例 
 
public class InsortSort {

    public static void sort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int num = a[i];
            int j;
            for (j = i; j > 0 && num < a[j - 1]; j--) {
                a[j] = a[j - 1];
            }
            a[j] = num;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 5};
        for (int i : arr) {
            System.out.printf(" "+i);
        }
        System.out.println();
        sort(arr);
        for (int i : arr) {
            System.out.printf(" "+i);
        }
    }
}
 
 

插入排序：
 
1）直接插入排序：
 
理解：假设有n个数需要排序，则第一个数已经排序，剩下的n-1个数没有排序，现在需要将剩下的n-1个数，一个一个找到合适的位置插入进去。
 
第一趟排序结束：得到已经排序的数字的个数是2，再加上剩下的n-2个数字
 
例如：待排序序列（49,38,65,97,76,13,27,49），第一趟排序结束（38 49 65 97 76 13 27 49 ）
 
直接插入排序实现java代码如下：
 
private static void ZSort(int a[]) {
        // TODO Auto-generated method stub
        /*
         * 直接插入排序算法 第一个元素已经排序，剩下n-1个没有排序, 一个一个比较 
         * 第一轮循环，执行n-1次 
         * 第二轮循环，当比他大后移，否则break
         */
        for (int i = 1; i < a.length; ++i) {
            int temp = a[i];
            int j = i - 1;
            for (; j >= 0; j--) {

                if (temp < a[j]) {
                    a[j + 1] = a[j];
                } else {
                    break;
                }
            }
            a[j + 1] = temp;
        }
    }

    public static void main(String[] args) {
        int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
        ZSort(a);
        for (int i : a) {
            System.out.print(i + " ");
        }
    }
 
（欢迎指正！再更新其他算法）