插入法

插入法，即插入的方法。實際生活中，有直接插和旋轉插兩種方法。數學上插入法即插值法。從要求的數在不在邊界來看，有內插和外插兩種；而從具體的算法看，又有線性插值和非線性插值。

插值的具體算法有很多，適用於不同的問題和精度要求。一般查數學物理用表，要求不高的話，可以用簡單的線性內插值。

線性內插值方法是：設線形關係式：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) )。顯然本式也適合外插計算。

三次以上拋物線內插法類似二次拋物線的形式。

用內插法估計計算，造成一定程度的誤差，如果誤差在精度範圍內，就可以用此值估算一個函數值，特別是超越函數。

解釋：一種算法

:將序列分為有序序列和無序列,依次從無序序列中取出元素值插入到有序序列的合適位置。初始是有序序列中只有第一個數,其餘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");

}

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