1.算法思想

直接插入排序是插入排序算法的一种，其基本思想是：所有数据分为已排序部分和待排序部分，每次取从待排序部分的第一个元素插入到已排序部分的合适位置。比较方法为：待排序元素从已排序部分的最右边开始比较，找到合适位置之后将其位置后的元素全部后移，然后插入位置。

待排序的元素中如果存在相同的元素，经过排序后，相同元素的相对次序如果保持不变，则称这种排序算法是稳定的，否则排序算法是不稳定的。

2.算法图解

初始状态时选取第一个元素归为已排序部分的第一个元素，其后的元素为待排序部分，从i=1开始每次从待排序元素中选取第一个在已排序的位置中找到自己的位置然后将其后的元素全部后移，再将元素插入其中。

直接插入排序

3.代码实现

• 以下是算法的C语言代码实现：

/*
    直接插入排序算法（升序）
 */
#include<stdio.h>
#include<stdlib.h>
void  insertSort(int *a,int len);
void insertSort(int *a,int len)
{
    int i,temp,j;
    for(i=1;i<len;i++)
    {
        temp = a[i];//存储当前待插入排序元素
        j = i-1;//从已排序的区间最右边开始比较
        while(j>=0&&a[j]>temp)
        {
            a[j+1] = a[j];//通过循环将大于待排序值的元素全部右移
            j--;
        }
        if(j!=i-1)
        {
            a[j+1] = temp;//待插入元素插入位置非现在所在位置，则插入空处
        }
    }

}

int main()
{
    int a[]={49,38,65,97,76,13,27,49};//待排序数组
    int len = sizeof(a)/(sizeof(a[0]));
    insertSort(a,len);
    for(int i=0;i<len;i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

• 以下是算法的Java代码实现：

package insertSort;

public class InsertSort {

    public static void sort(int a[])
    {
        int temp,i,j;
        for(i=0;i<a.length;i++)
        {
            temp = a[i];
            j = i-1;
            while(j>=0&&temp<a[j])
            {
                a[j+1] = a[j];
                j--;
            }
            if(j!=i-1)
            {
                a[j+1] = temp;
            }
        }
    }
    public static void main(String args[])
    {
        int []a = {49,38,65,97,76,13,27,59};
        InsertSort.sort(a);
        for(int element : a)
        {
            System.out.print(element+" ");
        }
    }
}

4.小结

直接插入排序是插入排序中最简单的一种算法，它的平均时间复杂度为T(n)=O(n^2)，辅助空间为S(n)=O(1)，算法中通过a[j]>temp找出插入位置，所以直接插入排序算法是稳定的。
如有不正确的地方请大神指正，谢谢大家！