1.顺序查找
/**顺序查找平均时间复杂度 O(n)
* @param searchKey 要查找的值
* @param array 数组(从这个数组中查找)
* @return 查找结果(数组的下标位置)
*/
public static int orderSearch(int searchKey,int[] array){
if(array==null||array.length<1)
return -1;
for(int i=0;i<array.length;i++){
if(array[i]==searchKey){
return i;
}
}
return -1;
}
2.二分查找
/**
* 二分查找又称折半查找,它是一种效率较高的查找方法。 【二分查找要求】:1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
*
* @param array
* 有序数组 *
* @param searchKey
* 查找元素 *
* @return searchKey的数组下标,没找到返回-1
*/
public static int binarySearch(int[] array, int searchKey) {
int low = 0;
int high = array.length - 1;
while (low <= high) {
int middle = (low + high) / 2;
if (searchKey == array[middle]) {
return middle;
} else if (searchKey < array[middle]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
return -1;
}
3.分块查找
a. 首先将查找表分成若干块,在每一块中数据元素的存放是任意的,但块与块之间必须是有序的(假设这种排序是按关键字值递增的,也就是说在第一块中任意一个数据元素的关键字都小于第二块中所有数据元素的关键字,第二块中任意一个数据元素的关键字都小于第三块中所有数据元素的关键字,依次类推);
b. 建立一个索引表,把每块中最大的关键字值按块的顺序存放在一个辅助数组中,这个索引表也按升序排列;
c. 查找时先用给定的关键字值在索引表中查找,确定满足条件的数据元素存放在哪个块中,查找方法既可以是折半方法,也可以是顺序查找。
d. 再到相应的块中顺序查找,便可以得到查找的结果。
/**
* 分块查找
*
* @param index
* 索引表,其中放的是各块的最大值
* @param st
* 顺序表,
* @param key
* 要查找的值
* @param m
* 顺序表中各块的长度相等,为m
* @return
*/
public static int blockSearch(int[] index, int[] st, int key, int m) {
// 在序列st数组中,用分块查找方法查找关键字为key的记录
// 1.在index[ ] 中折半查找,确定要查找的key属于哪个块中
int i = binarySearch(index, key);
if (i >= 0) {
int j = i > 0 ? i * m : i;
int len = (i + 1) * m;
// 在确定的块中用顺序查找方法查找key
for (int k = j; k < len; k++) {
if (key == st[k]) {
System.out.println("查询成功");
return k;
}
}
}
System.out.println("查找失败");
return -1;
}
4.哈希查找
哈希表查找是通过对记录的关键字值进行运算,直接求出结点的地址,是关键字到地址的直接转换方法,不用反复比较。假设f包含n个结点,Ri为其中某个结点(1≤i≤n),keyi是其关键字值,在keyi与Ri的地址之间建立某种函数关系,可以通过这个函数把关键字值转换成相应结点的地址,有:addr(Ri)=H(keyi),addr(Ri)为哈希函数。
解决冲突的方法有以下两种:
(1)开放地址法
如果两个数据元素的哈希值相同,则在哈希表中为后插入的数据元素另外选择一个表项。当程序查找哈希表时,如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素,程序就会继续往后查找,直到找到一个符合查找要求的数据元素,或者遇到一个空的表项。
(2)链地址法
将哈希值相同的数据元素存放在一个链表中,在查找哈希表的过程中,当查找到这个链表时,必须采用线性查找方法。
/****
* Hash查找
*
* @param hash
* @param hashLength
* @param key
* @return
*/
public static int searchHash(int[] hash, int hashLength, int key) {
// 哈希函数
int hashAddress = key % hashLength;
// 指定hashAdrress对应值存在但不是关键值,则用开放寻址法解决
while (hash[hashAddress] != 0 && hash[hashAddress] != key) {
hashAddress = (++hashAddress) % hashLength;
}
// 查找到了开放单元,表示查找失败
if (hash[hashAddress] == 0)
return -1;
return hashAddress;
}
/***
* 数据插入Hash表
*
* @param hash
* 哈希表
* @param hashLength
* @param data
*/
public static void insertHash(int[] hash, int hashLength, int data) {
// 哈希函数
int hashAddress = data % hashLength;
// 如果key存在,则说明已经被别人占用,此时必须解决冲突
while (hash[hashAddress] != 0) {
// 用开放寻址法找到
hashAddress = (++hashAddress) % hashLength;
}
// 将data存入字典中
hash[hashAddress] = data;
}
分享到:
相关推荐
《Java常用算法手册》分三篇,共13章,分别介绍了算法基础、算法应用和算法面试题。首先介绍了算法概述,然后重点分析了数据结构和基本算法思想;接着,详细讲解了算法在排序、查找、数学计算、数论、历史趣题、游戏...
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找 Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找
Java常用排序算法源码 稳定:冒泡排序、插入排序、归并排序和基数排序;不稳定:选择排序、快速排序、希尔排序、堆排序
第5章 查找算法 第6章 基本数学问题 第7章 数据结构问题 第8章 数论问题 第9章 算法经典趣题 **0章 游戏中的算法 **1章 密码学概述 **2章 压缩与解压缩算法 第3篇 算法面试篇 **3章 数学能力测试 **4章 算法面试题
查找算法 •1 概念 •2 顺序查找 •3 二分查找 •4 分块查找 •5 哈希表查找
接着,详细讲解了算法在排序、查找、数学计算、数论、历史趣题、游戏、密码学等领域中的应用:最后,列举了算法的一些常见面试题。书中知识点覆盖全面,结构安排紧凑,讲解详细,实例丰富。全书对每一个知识点都给出了相 ...
Java常用高效8大排序算法与二分法查找,适合正在学习算法和准备学习算法的算法爱好者和研究使用算法的开发人员使用。
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫...常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德...
十种常用算法之二分查找(java版)(csdn)————程序
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找(同步到博客).doc
在java中,我们常用的查找有四种: 顺序(线性)查找 二分查找/折半查找 插值查找 斐波那契查找 线性查找 思路: 如果在数组中发现满足条件的值, 就返回其下标 /** * 线性查找 * @author TimePause * @create 2020-02...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
* 顺序查找 * @param sz * @param key * @return 下标 */ public static int SequenceSearch(int[] sz, int key) { for (int i = 0; i < sz.length; i++) { if (sz[i] == key) { return i; } } return...
5.4.1 顺序表结构中的查找算法 145 5.4.2 链表结构中的查找算法 148 5.4.3 树结构中的查找算法 151 5.4.4 图结构中的查找算法 152 5.5 小结 153 第6章 基本数学问题 154 6.1 判断闰年 154 6.2 多项式计算 ...
Java实现的FTP连接与数据浏览程序,实现实例化可操作的窗口。 部分源代码摘录: ftpClient = new FtpClient(); //实例化FtpClient对象 String serverAddr=jtfServer.getText(); //得到服务器...