国家骨干高职院校建设网站,游戏网站建设与策划书,app开发与网站开发有何不同,扁平 wordpress1. 顺序查找2. 二分查找3. 插值查找4. 斐波那契查找5. 树表查找6. 分块查找7. 哈希查找
查找是在大量的信息中寻找一个特定的信息元素#xff0c;在计算机应用中#xff0c;查找是常用的基本运算#xff0c;例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查… 1. 顺序查找2. 二分查找3. 插值查找4. 斐波那契查找5. 树表查找6. 分块查找7. 哈希查找
查找是在大量的信息中寻找一个特定的信息元素在计算机应用中查找是常用的基本运算例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法说是七种其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在后续的博文中进行详细介绍。 查找定义根据给定的某个值在查找表中确定一个其关键字等于给定值的数据元素或记录。
查找算法分类 1静态查找和动态查找 注静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。 2无序查找和有序查找。 无序查找被查找数列有序无序均可 有序查找被查找数列必须为有序数列。 平均查找长度Average Search LengthASL需和指定key进行比较的关键字的个数的期望值称为查找算法在查找成功时的平均查找长度。 对于含有n个数据元素的查找表查找成功的平均查找长度为ASL Pi*Ci的和。 Pi查找表中第i个数据元素的概率。 Ci找到第i个数据元素时已经比较过的次数。
1. 顺序查找 说明顺序查找适合于存储结构为顺序存储或链接存储的线性表。
基本思想顺序查找也称为线形查找属于无序查找算法。从数据结构线形表的一端开始顺序扫描依次将扫描到的结点关键字与给定值k相比较若相等则表示查找成功若扫描结束仍没有找到关键字等于k的结点表示查找失败。
复杂度分析 查找成功时的平均查找长度为假设每个数据元素的概率相等 ASL 1/n(123…n) (n1)/2 ; 当查找不成功时需要n1次比较时间复杂度为O(n); 所以顺序查找的时间复杂度为O(n)。 C实现源码
//顺序查找
int SequenceSearch(int a[], int value, int n)
{int i;for(i0; in; i)if(a[i]value)return i;return -1;
} java实现源码 public class sequence{public static boolean SequenceSearch(int a[],int k,int value){for( int i 0 ; ik;i){if( value a[i])return true;elsereturn false;}return false;}public static void main(String[] args) {int[] a {8,2,4,5,3,10,11,6,9};System.out.println(SequenceSearch(a,a.length,20));}
}
//printf: falsepublic static boolean SequenceSearch(int a[],int k,int value){for( int i 0 ; ik;i){if( value a[i])return true;elsereturn false;}return false;}public static void main(String[] args) {int[] a {8,2,4,5,3,10,11,6,9};System.out.println(SequenceSearch(a,a.length,20));}
}
//printf: false2. 二分查找 说明元素必须是有序的如果是无序的则要先进行排序操作。 基本思想也称为是折半查找属于有序查找算法。用给定值k先与中间结点的关键字比较中间结点把线形表分成两个子表若相等则查找成功若不相等再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表这样递归进行直到查找到或查找结束发现表中没有这样的结点。 复杂度分析最坏情况下关键词比较次数为log2(n1)且期望时间复杂度为O(log2n) 注折半查找的前提条件是需要有序表顺序存储对于静态查找表一次排序后不再变化折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说维护有序的排序会带来不小的工作量那就不建议使用。——《大话数据结构》
C实现源码
//二分查找折半查找版本1
int BinarySearch1(int a[], int value, int n)
{int low, high, mid;low 0;high n-1;while(lowhigh){mid (lowhigh)/2;if(a[mid]value)return mid;if(a[mid]value)high mid-1;if(a[mid]value)low mid1;}return -1;
}//二分查找递归版本
int BinarySearch2(int a[], int value, int low, int high)
{int mid low(high-low)/2;if(a[mid]value)return mid;if(a[mid]value)return BinarySearch2(a, value, low, mid-1);if(a[mid]value)return BinarySearch2(a, value, mid1, high);
}
java 实现源码
/*1.*/
public class BinarySearch1{public static int binarysearch(int[] a,int n,int value){int low 0;int high n - 1;int mid;while(low high){mid (low high)/2;if(value a[mid])high mid - 1;if(value a[mid])low mid 1;if(value a[mid])return mid;}return -1;}public static void main(String[] args) {//int[] a {1,4,2,9,8,6,7,0,3,5}int[] a {0,1,2,3,4,5,6,7,8,9};System.out.println(binarysearch(a,a.length,7));}
} public static int binarysearch(int[] a,int n,int value){int low 0;int high n - 1;int mid;while(low high){mid (low high)/2;if(value a[mid])high mid - 1;if(value a[mid])low mid 1;if(value a[mid])return mid;}return -1;}public static void main(String[] args) {//int[] a {1,4,2,9,8,6,7,0,3,5}int[] a {0,1,2,3,4,5,6,7,8,9};System.out.println(binarysearch(a,a.length,7));}
}
/*2.recursive algorithm */
public class BinarySearch2{public static int binarysearch(int[] a,int value,int low,int high){int mid (low high)/2;if(value a[mid])return mid;mid (low high)/2;if(value a[mid])return binarysearch(a,value,low,mid - 1);if(value a[mid])return binarysearch(a,value,mid 1,high); return -1;}public static void main(String[] args) {//int[] a {1,4,2,9,8,6,7,0,3,5}int[] a {0,1,2,3,4,5,6,7,8,9};System.out.println(binarysearch(a,4,0,a.length-1));}
}
3. 插值查找 在介绍插值查找之前首先考虑一个新问题为什么上述算法一定要是折半而不是折四分之一或者折更多呢 打个比方在英文字典里面查“apple”你下意识翻开字典是翻前面的书页还是后面的书页呢如果再让你查“zoo”你又怎么查很显然这里你绝对不会是从中间开始查起而是有一定目的的往前或往后翻。 同样的比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5 我们自然会考虑从数组下标较小的开始查找。 经过以上分析折半查找这种查找方式不是自适应的也就是说是傻瓜式的。二分查找中查找点计算如下 mid(lowhigh)/2, 即midlow1/2*(high-low); 通过类比我们可以将查找的点改进为如下 midlow(key-a[low])/(a[high]-a[low])*(high-low) 也就是将上述的比例参数1/2改进为自适应的根据关键字在整个有序表中所处的位置让mid值的变化更靠近关键字key这样也就间接地减少了比较次数。 基本思想基于二分查找算法将查找点的选择改进为自适应选择可以提高查找效率。当然差值查找也属于有序查找。 注对于表长较大而关键字分布又比较均匀的查找表来说插值查找算法的平均性能比折半查找要好的多。反之数组中如果分布非常不均匀那么插值查找未必是很合适的选择。 复杂度分析查找成功或者失败的时间复杂度均为O(log2(log2n))。
java代码实现
public class InsertionSearch{public static int InsertionSearch(int[] a, int value, int low, int high){int mid low(value-a[low])/(a[high]-a[low])*(high-low);if(a[mid]value)return mid; if(a[mid]value)return InsertionSearch(a, value, low, mid-1);if(a[mid]value)return InsertionSearch(a, value, mid1, high);return -1;}public static void main(String[] args) {int[] a {0,1,2,3,4,5,6,7,8,9};System.out.println(InsertionSearch(a,2,0,a.length-1));}
} 4. 斐波那契查找
在介绍斐波那契查找算法之前我们先介绍一下很它紧密相连并且大家都熟知的一个概念——黄金分割。 黄金比例又称黄金分割是指事物各部分间一定的数学比例关系即将整体一分为二较大部分与较小部分之比等于整体与较大部分之比其比值约为1:0.618或1.618:1。 0.618被公认为最具有审美意义的比例数字这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。 大家记不记得斐波那契数列1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….从第三个数开始后边每一个数都是前两个数的和。然后我们会发现随着斐波那契数列的递增前后两个数的比值会越来越接近0.618利用这个特性我们就可以将黄金比例运用到查找技术中。 基本思想也是二分查找的一种提升算法通过运用黄金比例的概念在数列中选择查找点进行查找提高查找效率。同样地斐波那契查找也属于一种有序查找算法。 相对于折半查找一般将待比较的key值与第midlowhigh/2位置的元素比较比较结果分三种情况 1相等mid位置的元素即为所求 2lowmid1; 3highmid-1。 斐波那契查找与折半查找很相似他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1及nF(k)-1; 开始将k值与第F(k-1)位置的记录进行比较(及midlowF(k-1)-1),比较结果也分为三种 1相等mid位置的元素即为所求 2lowmid1,k-2; 说明lowmid1说明待查找的元素在[mid1,high]范围内k-2 说明范围[mid1,high]内的元素个数为n-(F(k-1)) Fk-1-F(k-1)Fk-F(k-1)-1F(k-2)-1个所以可以递归的应用斐波那契查找。 3highmid-1,k-1。 说明lowmid1说明待查找的元素在[low,mid-1]范围内k-1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个所以可以递归 的应用斐波那契查找。 复杂度分析最坏情况下时间复杂度为O(log2n)且其期望复杂度也为O(log2n)。
5. 树表查找 5.1 最简单的树表查找算法——二叉树查找算法。 基本思想二叉查找树是先对待查找的数据进行生成树确保树的左分支的值小于右分支的值然后在就行和每个节点的父节点比较大小查找最适合的范围。 这个算法的查找效率很高但是如果使用这种查找方法要首先创建树。 二叉查找树BinarySearch Tree也叫二叉搜索树或称二叉排序树Binary Sort Tree或者是一棵空树或者是具有下列性质的二叉树 1若任意节点的左子树不空则左子树上所有结点的值均小于它的根结点的值 2若任意节点的右子树不空则右子树上所有结点的值均大于它的根结点的值 3任意节点的左、右子树也分别为二叉查找树。 二叉查找树性质对二叉查找树进行中序遍历即可得到有序的数列。 不同形态的二叉查找树如下图所示 复杂度分析它和二分查找一样插入和查找的时间复杂度均为O(logn)但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候树没有保持平衡比如我们查找上图b中的“93”我们需要进行n次查找操作。我们追求的是在最坏的情况下仍然有较好的时间复杂度这就是平衡查找树设计的初衷。 下图为二叉树查找和顺序查找以及二分查找性能的对比图 基于二叉查找树进行优化进而可以得到其他的树表查找算法如平衡树、红黑树等高效算法
5.2 平衡查找树之2-3查找树2-3 Tree 2-3查找树定义和二叉树不一样2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)他保存1个key和左右两个自己点。对应3节点(3-node)保存两个Key2-3查找树的定义如下 1要么为空要么 2对于2节点该节点保存一个key及对应value以及两个指向左右节点的节点左节点也是一个2-3节点所有的值都比key要小右节点也是一个2-3节点所有的值比key要大。 3对于3节点该节点保存两个key及对应value以及三个指向左中右的节点。左节点也是一个2-3节点所有的值均比两个key中的最小的key还要小中间节点也是一个2-3节点中间节点的key值在两个跟节点key值之间右节点也是一个2-3节点节点的所有key值比两个key中的最大的key还要大。 2-3查找树的性质 1如果中序遍历2-3查找树就可以得到排好序的序列 2在一个完全平衡的2-3查找树中根节点到每一个为空节点的距离都相同。这也是平衡树中“平衡”一词的概念根节点到叶节点的最长距离对应于查找算法的最坏情况而平衡树中根节点到叶节点的距离都一样最坏情况也具有对数复杂度。 性质2如下图所示 复杂度分析 2-3树的查找效率与树的高度是息息相关的。
在最坏的情况下也就是所有的节点都是2-node节点查找效率为lgN在最好的情况下所有的节点都是3-node节点查找效率为log3N约等于0.631lgN距离来说对于1百万个节点的2-3树树的高度为12-20之间对于10亿个节点的2-3树树的高度为18-30之间。 对于插入来说只需要常数次操作即可完成因为他只需要修改与该节点关联的节点即可不需要检查其他节点所以效率和查找类似。下面是2-3查找树的效率 5.3 平衡查找树之红黑树Red-Black Tree 2-3查找树能保证在插入元素之后能保持树的平衡状态最坏情况下即所有的子节点都是2-node树的高度为lgn从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂于是就有了一种简单实现2-3树的数据结构即红黑树Red-Black Tree。 基本思想红黑树的思想就是对2-3查找树进行编码尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型红色链接他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的使用红色链接的两个2-nodes来表示一个3-nodes节点并且向左倾斜即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改和普通的二叉查找树相同。 红黑树的定义 红黑树是一种具有红色和黑色链接的平衡查找树同时满足
红色节点向左倾斜一个节点不可能有两个红色链接整个树完全黑色平衡即从根节点到所以叶子结点的路径上黑色链接的个数都相同。下图可以看到红黑树其实是2-3树的另外一种表现形式如果我们将红色的连线水平绘制那么他链接的两个2-node节点就是2-3树中的一个3-node节点了。 红黑树的性质整个树完全黑色平衡即从根节点到所以叶子结点的路径上黑色链接的个数都相同2-3树的第2性质从根节点到叶子节点的距离都相等。咋· 复杂度分析最坏的情况就是红黑树中除了最左侧路径全部是由3-node节点组成即红黑相间的路径长度是全黑路径长度的2倍。 下图是一个典型的红黑树从中可以看到最长的路径(红黑相间的路径)是最短路径的2倍 红黑树的平均高度大约为logn。 下图是红黑树在各种情况下的时间复杂度可以看出红黑树是2-3查找树的一种实现它能保证最坏情况下仍然具有对数的时间复杂度。 红黑树这种数据结构应用十分广泛在多种编程语言中被用作符号表的实现如
Java中的java.util.TreeMap,java.util.TreeSetC STL中的map,multimap,multiset.NET中的SortedDictionary,SortedSet等。待续....2018/02/26 参考文献http://www.cnblogs.com/maybe2030/p/4715035.html#_labelTop
