[科普中国]-初等算法

简介

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。在计算机科学中，初等算法是指一些基本的算法，这些算法提供了一般理论最好的例子，但在总体发展中得到很少关注。1初等算法一般具有以下特点：简明、初等。常见的有插入排序、快速排序、顺序查找、二叉树查找等。

算法算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

一个算法应该具有以下五个重要的特征：

算法有穷性（Finiteness）算法的有穷性是指算法必须能在执行有限个步骤之后终止；

算法确切性(Definiteness)算法的每一步骤必须有确切的定义；

算法输入项(Input)一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；

算法输出项(Output)一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

算法可行性(Effectiveness)算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。2

常见的初等算法插入排序有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。

查找算法顺序查找

⒈顺序查找的思想是：

将查找值顺序逐个与结点值进行比较，相等即为查找成功，否则查找失败.

程序如下：

program sxcz;const n=7;typearr=array[1..n] of integer;var x1,i:integer;a:arr;b:boolean;place:integer;procedure search(r:arr;m,x:integer; varfound:boolean;var p:integer);beginp:=1;found:=false;while(p0 dobeginj:=k-1;k:=0;for i:=1 to j doif r[i]>r[i+1] thenbegin t:=r[i];a[i]:=r[i+1];r[i+1]:=t;k:=i;end;end;end;procedure search(r:arr;m,x:integer; var p:integer);var low,high,mid:integer;beginp:=0;low:=1;high:=m;while lowr[mid] then low:=mid+1 elseif x=w then maketr(d,right) else maketr(d,left);end;function searchtr(x:integer;p:point):boolean;beginif p=nil then searchtr:=falseelse if x=p^.w then searchtr:=trueelse if x