㈠ 几种查找算法的比较
文章摘要: 查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，文中介绍四种查找算法，分别是顺序查找、二分查找、二叉排序树查找和哈希查找。并用JAVA语言编写了相应程序代码，比较了查找同一个数据的时间复杂度和空间复杂度。
㈡ 数据结构：重要的查找算法有哪些
折半查找也就是二分查找，它必须满足排序关系。
查找也可以用二叉查找树，一般复杂度为O(logn),最坏为O(n)。
也可用平衡树进行查找，如AVL,Treap,Splay等，可以做到保持O(logn)。
比二分查找性能更优的：大概只有Hash了吧。如果Hash函数设计的好，基本可以认为是O(1)
堆排序比较有意思，值得研究一下，理解了后，很有用～，也很重要。
㈢ 常见的数据检索算法有哪些数据库都采用什么样的检索方式如何提高检索的效率
信息检索方法包括：普通法、追溯法和分段法。1、普通法是利用书目、文摘、索引等检索工具进行文献资料查找的方法。运用这种方法的关键在于熟悉各种检索工具的性质、特点和查找过程，从不同角度查找。普通法又可分为顺检法和倒检法。2、追溯法是利用已有文献所附的参考文献不断追踪查找的方法，在没有检索工具或检索工具不全时，此法可获得针对性很强的资料，查准率较高，查全率较差。3、分段法是追溯法和普通法的综合，它将两种方法分期、分段交替使用，直至查到所需资料为止。(3)常见的查找算法扩展阅读检索原因信息检索是获取知识的捷径美国普林斯顿大学物理系一个年轻大学生名叫约瀚·菲利普，在图书馆里借阅有关公开资料，仅用四个月时间，就画出一张制造原子弹的设计图。他设计的原子弹，体积小(棒球大小)、重量轻(7.5公斤)、威力大(相当广岛原子弹3/4的威力)，造价低(当时仅需两千美元)，致使一些国家（法国、巴基斯坦等）纷纷致函美国大使馆，争相购买他的设计拷贝。二十世纪七十年代，美国核专家泰勒收到一份题为《制造核弹的方法》的报告，他被报告精湛的技术设计所吸引，惊叹地说：“至今我看到的报告中，它是最详细、最全面的一份。”
㈣ 几种常见的查找算法之比较
二分法平均查找效率是O(logn)，但是需要数组是排序的。如果没有排过序，就只好先用O（nlogn)的预处理为它排个序了。而且它的插入比较困难，经常需要移动整个数组，所以动态的情况下比较慢。
哈希查找理想的插入和查找效率是O(1)，但条件是需要找到一个良好的散列函数，使得分配较为平均。另外，哈希表需要较大的空间，至少要比O(n)大几倍，否则产生冲突的概率很高。
二叉排序树查找也是O(logn)的，关键是插入值时需要做一些处理使得它较为平衡（否则容易出现轻重的不平衡，查找效率最坏会降到O(n)），而且写起来稍微麻烦一些，具体的算法你可以随便找一本介绍数据结构的书看看。当然，如果你用的是c语言，直接利用它的库类型map、multimap就可以了,它是用红黑树实现的，理论上插入、查找时间都是O(logn)，很方便，不过一般会比自己实现的二叉平衡树稍微慢一些。
㈤ 查找算法有哪些
查找算法常用的有，顺序查找，二分查找，哈希表查找，等等。
㈥ 查找算法有哪两种类型
二分查找又称折半查找，它是一种效率较高的查找方法。
分块查找又称索引顺序查找，它是顺序查找的一种改进方法。
方法描述：将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……。
㈦ 查找的计算机算法
⒈顺序查找的思想是：
将查找值顺序逐个与结点值进行比较，相等即为查找成功，否则查找失败.
程序如下：
program sxcz;
const n=7;
type
arr=array[1..n] of integer;
var x1,i:integer;
a:arr;
b:boolean;
place:integer;
procere search(r:arr;m,x:integer; var found: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('Place of',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;
procere 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;
procere 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;
procere 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. 以上讲的查找方法基于比较的，查找效率依赖比较次数，其实理想的查找希望不经比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，这样查找k时，只要根据这个对应关系f找到给定值k的像f(k）。这种对应关系f叫哈希（hash）函数。按这种思想建立的表叫哈希表（也叫散列表）。哈希表存取方便但存储时容易冲突（collision）：即不同的关键字可以对应同一哈希地址。如何确定哈希函数和解决冲突是关键。
⒈哈希函数的构造方法
直接寻址法：H(k)=k 或H(k)=a*k+b（线形函数）
如：人口数字统计表 地址 1 2 3 ... 100 年龄 1 2 3 ... 100 人数 67 3533 244 ... 4 数字分析法：取关键字的若干数位组成哈希地址
如：关键字如下：若哈希表长为100则可取中间两位10进制数作为哈希地址。 81346532 81372242 81387422 81301367 81322817 81338967 81354157 81368537 平方取中法：关键字平方后取中间几位数组成哈希地址
折叠法：将关键数字分割成位数相同的几部分（最后一部分的位数可以不同）然后取几部分的叠加和（舍去进位）作为哈希地址。
除留余数法：取关键字被某个不大于表长m的数p除后所得的余数为哈希地址。
H(k)=k mod p p<=m
随机数法：H(k)=rondom(k）。
⒉处理冲突的方法
假设地址集为0..n-1，由关键字得到的哈希地址为j(0<=j<=n-1）的位置已存有记录，处理冲突就是为该关键字的记录找到另一个空的哈希地址。在处理中可能得到一个地址序列Hi i=1，2，...k
0<=Hi<=n-1），即在处理冲突时若得到的另一个哈希地址H1仍发生冲突，再求下一地址H2，若仍冲突，再求H3...。怎样得到Hi呢？
开放寻址法：Hi=(H(k)+di) mod m （H(k）为哈希函数；m为哈希表长；di为增量序列）
当di=1，2，3，... m-1 时叫线性探测再散列。
当di=1，-1，2，-2，3，-3，...,k,-k时叫二次探测再散列。
当di=random（m）时叫伪随机探测序列。
例：长度为11的哈希表关键字分别为17，60，29，哈希函数为H(k)=k mod 11，第四个记录的关键字为38，分别按上述方法添入哈希表的地址为8，4，3（随机数=9）。
再哈希法：Hi=RHi(key) i=1,2,...,k，其中RHi均为不同的哈希函数。
链地址法：这种方法很象基数排序，相同的地址的关键字值均链入对应的链表中。
建立公益区法：另设一个溢出表，不管得到的哈希地址如何，一旦发生冲突，都填入溢出表。
⒊哈希表的查找
例：如下一组关键字按哈希函数H(k)=k mod 13和线性探测处理冲突所得的哈希表a[0..15]: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 01 68 27 55 19 20 84 79 23 11 10 当给定值k=84，则首先和a[6]比在依次和a[7],a[8]比结果a[8]=84查找成功。
当给定值k=38，则首先和a[12]比，再和a[13]比，由于a[13]没有，查找不成功，表中不存在关键字等于38的记录。 查找第k小元素即在n个元素中（未排序）找到第k小的元素。方法同快速排序，采用递归方式。
程序如下：
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
b:arr;
i,k:integer;
function p(s,t:integer):integer;
var i,j,t1,x:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
p:=i;
end;
function find(s,t,k:integer):integer;
var p1,q:integer;
begin
if s=t then find:=b[s] else
begin
p1:=p(s,t);
q:=p1-s+1;
if k<=q then find:=find(s,p1,k) else find:=find(p1+1,t,k-q);
end;
end;
begin
write('input data:');
for i:=1 to n do read(b[i]);readln;
write('input k:');read(k);
write('output data:');
writeln('kthsmall:=',find（1,n,k));
end.
㈧ 【数据结构】几种重要的查找算法。
恩你是要问什么?
顺序查找就是按顺序查找,复杂度O(n)
二分查找的前提是数据是有序的 一次复杂度O(logn)
例如在数组 A: 1 3 5 7 8 10 12 中
如果要找 10
我们先看中间的数是 7, 10比7大,那么继续在右侧二分寻找,这是一个递归的过程.
伪代码:
bool find(int L,int R,int What_You_Want) {
if (L > R) return false;
int mid = (L + R) / 2
if (A[mid] == What_You_Want) return true;
else if (A[mid] > What_You_Want) return find(L,mid - 1,What_You_Want);
else return find(mid + 1, R, What_You_Want);
}
二叉搜索树的原理与二分查找相同
㈨ 数据结构有哪些基本算法
数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。
可以理解为：程序设计 = 数据结构 + 算法
数据结构算法具有五个基本特征：输入、输出、有穷性、确定性和可行性。
1、输入：一个算法具有零个或者多个输出。以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。后面一句话翻译过来就是，如果一个算法本身给出了初始条件，那么可以没有输出。比如，打印一句话：NSLog(@"你最牛逼！");
2、输出：算法至少有一个输出。也就是说，算法一定要有输出。输出的形式可以是打印，也可以使返回一个值或者多个值等。也可以是显示某些提示。
3、有穷性：算法的执行步骤是有限的，算法的执行时间也是有限的。
4、确定性：算法的每个步骤都有确定的含义，不会出现二义性。
5、可行性：算法是可用的，也就是能够解决当前问题。
数据结果的基本算法有：
1、图搜索（广度优先、深度优先）深度优先特别重要
2、排序
3、动态规划
4、匹配算法和网络流算法
5、正则表达式和字符串匹配
6、三路划分-快速排序
7、合并排序（更具扩展性，复杂度类似快速排序）
8、DF/BF 搜索 （要知道使用场景）
9、Prim / Kruskal （最小生成树）
10、Dijkstra （最短路径算法）
11、选择算法
