算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。在計算機科學中，初等算法是指一些基本的算法，這些算法提供了一般理論最好的例子，但在總體發展中得到很少關注。初等算法一般具有以下特點：簡明、初等。
基本介紹
- 中文名：初等算法
- 外文名：Elementary Algorithm
- 學科：計算機科學、數學
- 定義：基本理論的實現
- 其他：書名
- 類別：排序、查找
簡介,算法,常見的初等算法,插入排序,查找算法,
簡介
算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。在計算機科學中，初等算法是指一些基本的算法，這些算法提供了一般理論最好的例子，但在總體發展中得到很少關注。初等算法一般具有以下特點：簡明、初等。常見的有插入排序、快速排序、順序查找、二叉樹查找等。
算法
算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規範的輸入，在有限時間內獲得所要求的輸出。如果一個算法有缺陷，或不適合於某個問題，執行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優劣可以用空間複雜度與時間複雜度來衡量。
算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在內的一些算法，包含了一些隨機輸入。
一個算法應該具有以下五個重要的特徵：
算法有窮性（Finiteness）算法的有窮性是指算法必須能在執行有限個步驟之後終止；
算法確切性(Definiteness)算法的每一步驟必須有確切的定義；
算法輸入項(Input)一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定出了初始條件；
算法輸出項(Output)一個算法有一個或多個輸出，以反映對輸入數據加工後的結果。沒有輸出的算法是毫無意義的；
算法可行性(Effectiveness)算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步，即每個計算步都可以在有限時間內完成（也稱之為有效性）。
常見的初等算法
插入排序
有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入後此數據序列仍然有序，這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，算法適用於少量數據的排序，時間複雜度為O(n^2)。是穩定的排序方法。插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但將最後一個元素除外（讓數組多一個空間才有插入的位置），而第二部分就只包含這一個元素（即待插入元素）。在第一部分排序完成後，再將這個最後元素插入到已排好序的第一部分中。插入排序的基本思想是：每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的檔案中適當位置上，直到全部插入完為止。包括：直接插入排序，二分插入排序（又稱折半插入排序），鍊表插入排序，希爾排序（又稱縮小增量排序）。
查找算法
順序查找
⒈順序查找的思想是：
將查找值順序逐個與結點值進行比較，相等即為查找成功，否則查找失敗.
程式如下：
program sxcz;
const n=7;
type
arr=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);
begin
p:=1;found:=false;
while(p<=m) and not found do
if r[p]=x then found:=true else p:=p+1;
end;
begin
write('Enter array:');
for i:=1 to n do read(a[i]);
writeln;
write('Enter search data:');
read(x1）；
search(a,n,x1,b,place);
if b then begin writeln('yes');
writeln('Placeof',x1:5,'is:',place); end
else writeln('no');
end.
查找二分查找
⒈二分查找的基本思想：首先將結點按關鍵字排序，其次將查找值與中間位置的值比較，相等，查找成功；不等，則中間數據大於或小於查找值，無論怎樣查找將在一半的數據中查找。
⒉例：輸入序列數據查找指定值.
程式：
program sxcz;
const n=7;
type
arr=
array[1..n] of integer;
var x1,i:integer;
a:arr;
place:integer;
procedure paixv(var r:arr;m:integer);
var k,j,i,t:integer;
begin
k:=m;
while k>0 do
begin
j:=k-1;k:=0;
for i:=1 to j do
if r[i]>r[i+1] then
begin 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;
begin
p:=0;low:=1;high:=m;
while low<=high do
begin
mid:=(low+high) div 2;
if x>r[mid] then low:=mid+1 else
if x<r[mid] then high:=mid-1 else
begin p:=mid;exit;end;
end;
end;
begin
write('Enter array:');
for i:=1 to n do read(a[i]);
writeln;
write('Enter search data:');
read(x1）；
paixv(a,n);
search(a,n,x1,place);
if place<>0 then writeln('yes') else writeln('no');
end.
查找二叉排序樹查找
program pxtree;
const
a:array[1..8] of integer=（10,18,3,8,12,2,7,3）；
type point=^nod;
nod=record
w:integer;
right,left:point ;
end;
var root,first:point;k:
boolean;i,x:integer;
procedure maketr(d:integer;var p:point);
begin
if p=nil then
begin
new(p);
with p^ do begin w:=d;right:=nil;left:=nil end;
if k then begin root:=p; k:=false end;
end
else with p^ do if d>=w then maketr(d,right) else maketr(d,left);
end;
function searchtr(x:integer;p:point):
boolean;
begin
if p=nil then searchtr:=false
else if x=p^.w then searchtr:=true
else if x<p^.w then searchtr:=searchtr(x,p^.left)
else searchtr:=searchtr(x,p^.right);
end;
begin
first:=nil;k:=true;
for i:=1 to 8 do maketr(a[i],first);
write('want find data x:');read(x);
if searchtr(x,first) then writeln('yes') else writeln('No');
end.
哈希（Hash）表
以上講的查找方法基於比較的，查找效率依賴比較次數，其實理想的查找希望不經比較，一次存取便能得到所查記錄，那就必須在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關係f，這樣查找k時，只要根據這個對應關係f找到給定值k的像f（k）。這種對應關係f叫哈希（hash）函式。按這種思想建立的表叫哈希表（也叫散列表）。哈希表存取方便但存儲時容易衝突（collision）：即不同的關鍵字可以對應同一哈希地址。如何確定哈希函式和解決衝突是關鍵。
