插入法是什么？
排序算法插入法插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张＃includeiostream.hvoidInsertSort(int*pData，intCount){intiTemp;intiPos;for(inti1;iCount;i++){iTemppData;//保存要插入的数iPosi-1;//被插入的数组数字个数while((iPos0)(iTemppData)){//从最后一个（最大数字）开始对比，大于它的数字往后移位pDatapData;iPos--;}pDataiTemp;//插入数字的位置}}voidmain(){intdata{10，9，8，7，6，5，4};InsertSort(data，7);for(inti0;i7;i++)coutdata;cout＼n;}其他：第一轮：8，10，7，9-8，10，7，9(交换0次)(循环1次)第二轮：9，10，8，7-8，9，10，7（交换1次)（循环2次)第一轮：8，9，10，7-7，8，9，10（交换1次)（循环3次)循环次数：6次交换次数：3次其他：第一轮：8，10，7，9-8，10，7，9（交换0次)（循环1次)第二轮：8，10，7，9-7，8，10，9（交换1次)（循环2次)第一轮：7，8，10，9-7，8，9，10（交换1次)（循环1次)循环次数：4次交换次数：2次上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是，因为其循环次数虽然并不固定，我们仍可以使用O方法
即插值法。从要求的数在不在边界来看，有内插和外插两种；而从具体的算法看，又有线性插值和非线性插值。
插值的具体算法有很多，适用于不同的问题和精度要求。一般查数学物理用表，要求不高的话，可以用简单的线性内插值。
线性内插值方法是：设要查的关系是y = f(x)，要查在x = x0点的数。但已知f(x1)和f(x2)，其中x1
( f(x0) - f(x1) ) / (x0 - x1) == ( f(x2) - f(x1) ) / (x2 - x1)
得到。
即有
f(x0) = ((x0 - x1) / (x2 - x1)) * ( f(x2) - f(x1) ) + f(x1)
这就是所要求的插值点。
楼主不难将仿照此方法做出线性外插值。
标签：插入法
