插入法又称"最远插入法"，原本是Mole和Jameson于1976年所提出，用于求解车辆路线问题(Vehicle Routing Problem,VRP)的方法，其结合最邻近法与节省法的观念，依序将顾客点插入路径中以构建配送路线。该算法的特点是在寻找插入位置的同时完成元素的移动。因为元素的移动必须从后往前,则可将两个操作结合在一起完成，提高算法效率。

• 中文名称 插入法
• 又称 "最远插入法"
• 提出者 Mole和Jameson
• 提出时间 1976年

数学

　　value-inserting method

　　插入法，即插入的方法。实际生活中，有直接插和旋转插两种方法。数学上插入法即插值法。从要求的数在不在边界来看，有内插和外插两种;而从具体的算法看，又有线性插值和非线性插值。

　　插值的具体算法有很多，适用于不同的问题和精度要求。一般查数学物理用表，要求不高的话，可以用简单的线性内插值。

　　线性内插值方法是:设线形关系式:y = f(x)，要计算在x = x0点的函数值。已知f(x1)和f(x2)，其中x1 < x0 < x2，则在x0点的值:f(x0)= f(x1)* ( x2- x0) / (x2 - x1) +f(x2) *( x1- x0) / ( x1- x2) ，这就是所要求的插值点的值。本式也适合外插。

　　二次抛物线内插法:设二次抛物线关系式:y = f(x)，要计算在x = x0点的函数。已知f(x1)、f(x2)和f(x3)，其中x1 < x2 < x3，x1 < x0 < x3，则在x0点的函数值:f(x0)= f(x1)*(x2-x0 ) *( x3- x0) / ((x3 - x1) *(x2 - x1) )+f(x2) *( x1- x0)*( x3- x0) / ((x3 - x2) *(x1 - x2) ) +f(x3)*(x2-x0 ) *( x1- x0) / ((x1 -x3 ) *( x2- x3) )。显然本式也适合外插计算。

　　三次以上抛物线内插法类似二次抛物线的形式。

　　用内插法估计计算，造成一定程度的误差，如果误差在精度范围内，就可以用此值估算一个函数值，特别是超越函数。

C语言

　　解释:一种算法

算法分析

　　:将序列分为有序序列和无序列,依次从无序序列中取出元素值插入到有序序列的合适位置。初始是有序序列中只有第一个数,其余n-1个数组成无序序列,则n个数需进n-1次插入。寻找在有序序列中插入位置可以从有序序列的最后一个数往前找,在未找到插入点之前可以同时向后移动元素,为插入元素准备空间。

示例算法

　　要求:用插入排序法对10个整数进行降序排序。

　　示例源代码

　　#include <stdio.h>

　　main()

　　{

　　int a[10],i,j,t;

　　printf("Please input 10 numbers: ");

　　for(i=0;i<10;i++)

　　scanf("%d",&a[i]);

　　for(i=1;i<10;i++) /*外循环控制趟数?n个数从第2个数开始到最后共进行n-1次插入*/

　　{

　　t=a[i]; /*将待插入数暂存于变量t中*/

　　for( j=i-1 ; j>=0 && t>a[j] ; j-- ) /*在有序序列?下标0 ~ i-1?中寻找插入位置*/

　　a[j+1]=a[j]; /*若未找到插入位置?则当前元素后移一个位置*/

　　a[j]=t; /*找到插入位置?完成插入*/

　　}

　　printf("The sorted numbers: ");

　　for(i=0;i<10;i++)

　　printf("%d ",a[i]);

　　printf("n");

　　}

算法特点

　　每趟从无序序列中取出第一个数插入到有序序列的合适位置,元素的最终位置在最后一趟插入后才能确定位置。也可先用循环查找插入位置,从前往后或从后往前,再将插入位置之后的元素,有序列中逐个后移一个位置,最后完成插入。该算法的特点是在寻找插入位置的同时完成元素的移动。因为元素的移动必须从后往前,则可将两个操作结合在一起完成，提高算法效率。仍可进行升序或降序排序。