插入法

插入法又称“最远插入法”，原本是Mole和Jameson于1976年所提出，用于求解车辆路线问题（Vehicle Routing Problem,VRP）的方法，其结合最邻近法与节省法的观念，依序将顾客点插入路径中以构建配送路线。

数学

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

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");

}

算法特点

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