概述

• 将新元素插入到有序序列中。

  步骤

• 假设序列中第一个元素为有序序列，将其余元素都当做待插入元素处理
• 每次当前待插入元素与有序序列最后一个元素开始依次进行比较，如果小于被比较元素，则进行交换，交换后继续进行比较直至有序序列第一个元素
• 将列表分为有序区，待插入的无序区

代码实现

Python 插入排序

def sort_cr(v_list):
    for i in range(len(v_list)):
        for j in range(i,0,-1):
            if v_list[j] < v_list[j-1]:
                v_list[j],v_list[j-1] = v_list[j-1],v_list[j]
    return v_list

C 插入排序

void svoid insertion_sort(int array[],int first,int last)
{
    int i,j;
    int temp;
    for(i=first+1;i<last;i++)
    {
        temp=array[i];
        j=i-1;
        //与已排序的数逐一比较，大于temp时，该数移后
        while((j>=0)&&(array[j]>temp))
        {
            array[j+1]=array[j];
            j--;
        }
        //存在大于temp的数
        if(j!=i-1)
            array[j+1]=temp;
    }
}

性能分析

时间复杂度

时间复杂度为O(n^2)

算法稳定性

• 比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。
• 如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。
• 相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，排序是稳定的。