插入法

插入法又稱“最遠插入法”，原本是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");
}

算法特點

每趟從無序序列中取出第一個數插入到有序序列的合適位置,元素的最終位置在最後一趟插入後才能確定位置。也可先用循環查找插入位置,從前往後或從後往前,再將插入位置之後的元素,有序列中逐個後移一個位置,最後完成插入。該算法的特點是在尋找插入位置的同時完成元素的移動。因為元素的移動必須從後往前,則可將兩個操作結合在一起完成，提高算法效率。仍可進行升序或降序排序。