Exploring
首页
  • Java

    • 面向对象的思想OOP
    • 浅谈Java反射原理
    • endorsed覆盖JDK中的类
  • 认证与授权

    • LDAP概念和原理介绍
    • OAuth2介绍
  • Impala

    • Impala 介绍
  • MySQL

    • 关于MySQL的一些面试题
    • 解决MySQL不到中文数据
    • 数据库之事务与实现原理
  • Oracle

    • oracle的表空间,用户管理,表操作,函数
    • oracle的查询、视图、索引
    • plsql简单入门
  • Redis

    • 数据类型详解
    • 跳越表
    • 数据持久化的两种方式
  • 共识算法

    • gossip
  • RPC

    • GRPC初识与快速入门
    • ProtocolBuffer基本语法
  • RabbitMQ

    • RabbitMQ入门程序之HelloWorld
    • RabbitMQ之工作模式
  • Zookeeper

    • Zookeeper一文入门
  • Docker

    • Docker入门初体验
  • Maven

    • 把自己的包到Maven中央仓库
    • Maven之自定义插件
  • Nginx

    • nginx的安装
    • nginx的配置文件
    • nignx 的变量
  • Tomcat

    • Servlet3通过SPI进行注册组件
  • Vagrant

    • vagrant 初始化
    • vagrant 常用配置
    • vagrant 自己制作 box
  • Linux

    • 启动方式 Systemd
    • 后台服务
    • 防火墙与 Iptables
  • 设计模式

    • 设计模式-代理
    • 设计模式-单例模式
    • 设计模式-迭代器
  • 分布式

    • CAP 理论
  • 数据结构

    • 数据结构之堆Heap
    • 数据结构之哈希表
    • 数据结构之队列
  • 计算机网络

    • HTTP与HTTPS详解
    • 浅谈DNS协议
    • ISP中的网络层
  • 算法

    • 常用查找算法及Java实现
    • 常用排序算法及Java实现
    • 迪杰斯特拉算法
  • 操作系统

    • 操作系统之进程调度算法
    • 操作系统之进程通讯IPC
    • 操作系统之内存管理
  • 抓包

    • 生成安卓系统证书
  • 加解密

    • 常见加密算法
    • 公开秘钥基础知识
    • RSA 解析
  • Windows

    • scoop 包管理
    • windows-terminal 配置
    • 增强 PowerShell
归档
Github (opens new window)
首页
  • Java

    • 面向对象的思想OOP
    • 浅谈Java反射原理
    • endorsed覆盖JDK中的类
  • 认证与授权

    • LDAP概念和原理介绍
    • OAuth2介绍
  • Impala

    • Impala 介绍
  • MySQL

    • 关于MySQL的一些面试题
    • 解决MySQL不到中文数据
    • 数据库之事务与实现原理
  • Oracle

    • oracle的表空间,用户管理,表操作,函数
    • oracle的查询、视图、索引
    • plsql简单入门
  • Redis

    • 数据类型详解
    • 跳越表
    • 数据持久化的两种方式
  • 共识算法

    • gossip
  • RPC

    • GRPC初识与快速入门
    • ProtocolBuffer基本语法
  • RabbitMQ

    • RabbitMQ入门程序之HelloWorld
    • RabbitMQ之工作模式
  • Zookeeper

    • Zookeeper一文入门
  • Docker

    • Docker入门初体验
  • Maven

    • 把自己的包到Maven中央仓库
    • Maven之自定义插件
  • Nginx

    • nginx的安装
    • nginx的配置文件
    • nignx 的变量
  • Tomcat

    • Servlet3通过SPI进行注册组件
  • Vagrant

    • vagrant 初始化
    • vagrant 常用配置
    • vagrant 自己制作 box
  • Linux

    • 启动方式 Systemd
    • 后台服务
    • 防火墙与 Iptables
  • 设计模式

    • 设计模式-代理
    • 设计模式-单例模式
    • 设计模式-迭代器
  • 分布式

    • CAP 理论
  • 数据结构

    • 数据结构之堆Heap
    • 数据结构之哈希表
    • 数据结构之队列
  • 计算机网络

    • HTTP与HTTPS详解
    • 浅谈DNS协议
    • ISP中的网络层
  • 算法

    • 常用查找算法及Java实现
    • 常用排序算法及Java实现
    • 迪杰斯特拉算法
  • 操作系统

    • 操作系统之进程调度算法
    • 操作系统之进程通讯IPC
    • 操作系统之内存管理
  • 抓包

    • 生成安卓系统证书
  • 加解密

    • 常见加密算法
    • 公开秘钥基础知识
    • RSA 解析
  • Windows

    • scoop 包管理
    • windows-terminal 配置
    • 增强 PowerShell
归档
Github (opens new window)
  • 数据结构

  • 计算机网络

  • 算法

    • 常用查找算法及Java实现
      • 常用算法
        • 顺序查找
        • 二分查找
      • 插值查找
      • 斐波那契查找
      • 树表查找
        • 二叉查找树
        • 平衡查找树之2-3查找树(2-3 Tree)
      • 分块查找
      • 哈希查找
    • 常用排序算法及Java实现
    • 迪杰斯特拉算法
    • 一致性哈希算法
    • DFS-深度优先-与BFS-广度优先-算法
    • LRU算法的Java实现
    • CRC16 算法
  • 操作系统

  • 基础
  • 算法
unclezs
2020-07-31
0
目录

常用查找算法及Java实现

# 常用算法

# 顺序查找

顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点,表示查找失败。

顺序查找的时间复杂度为O(n)。

public class Search {
    public static void main(String[] args) {
        int arr[] = {5, 11, 7, 9, 2, 3, 12, 8, 6, 1, 4, 10};
        search(arr,3);
    }

    /**
     * 顺序查找
     */
    public static int order(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 二分查找

也称为是折半查找,属于有序查找算法。用给定值k先与中间结点的关键字比较,中间结点把线形表分成两个子表,若相等则查找成功;若不相等,再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表,这样递归进行,直到查找到或查找结束发现表中没有这样的结点。

最坏情况下,关键词比较次数为log2(n+1),且期望时间复杂度为O(log2n);

   /**
     * 常规二分查找
     */
    public static int half(int[] arr, int target) {
        //使数组有序
        Arrays.sort(arr);
        System.out.println(String.format("原数组%s中查找【%s】", Arrays.toString(arr), target));
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target > arr[mid]) {
                left = mid + 1;
            } else if (target < arr[mid]) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 递归二分查找
     * @param high len-1
     */
    public static int halfByRecurse(int[] arr, int target, int low, int high) {
        int mid = ((high - low) >> 1) + low;
        if (low == high) {
            return -1;
        }
        if (target == arr[mid]) {
            return mid;
        }
        if (target > arr[mid]) {
            return halfByRecurse(arr, target, mid + 1, high);
        }
        if (target < arr[mid]) {
            return halfByRecurse(arr, target, low, mid - 1);
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

# 插值查找

基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。当然,差值查找也属于有序查找 代码基本上和二分查找一样,有修改的地方就是mid的获取

在二分查找中mid=mid=mid=low+high2low+high \over {2}2low+high​ 可改写成 $mid =low + $ $ {high-low} \over {2}$

也就是说我们的mid每次都是折中的取,但是对于一些均匀分布的有序表,这样做感觉有些费时,比如找字典的时候,找a这个字母,我们肯定不会从中间开始,而是偏向于字典前面一些开始。

插值查找就是基于这样的思想 我们对1/2进行改进:

mid=low+mid=low+mid=low+key−a[low]a[high]=a[low]key-a[low] \over a[high]=a[low]a[high]=a[low]key−a[low]​(high−low)(high-low)(high−low)

key就是要查找的值,数组a是有序表

简单的理解就是计算出key所占比,然后更好地找到key所在的区间范围 但是对于极端分布的数组,插值查找的效率就大打折扣了 比如

int a[7]={0,1,2,100,102,1000,10000}
1

Java代码实现

    /**
     * 插值查找
     */
    public static int insert(int[] arr, int target) {
        //使数组有序
        Arrays.sort(arr);
        System.out.println(String.format("原数组%s中进行插值查找【%s】", Arrays.toString(arr), target));
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) * ((target - arr[left]) / (arr[right] - arr[left]));
            if (target > arr[mid]) {
                left = mid + 1;
            } else if (target < arr[mid]) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 递归插值查找
     *
     * @param high len-1
     */
    public static int insertByRecurse(int[] arr, int target, int low, int high) {
        int mid = low + (high - low) * ((target - arr[low]) / (arr[high] - arr[low]));
        if (low <= high) {
            if (target == arr[mid]) {
                return mid;
            } else if (target > arr[mid]) {
                return insertByRecurse(arr, target, mid + 1, high);
            } else {
                return insertByRecurse(arr, target, low, mid - 1);
            }
        } else {
            return -1;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

# 斐波那契查找

斐波那契查找原理: 该查找原理与二分查找和插值查找类似,仅仅改变中间节点middle位置,middle位置不再是中间或插值得到,而是位于黄金分割点附近,即mid = low + F(k - 1) - 1(F,斐波那契数列)。

F(k-1)-1的说明

  • 由斐波那契数列F[k]=F[k-1] + F[k-2],可以得到F[k]-1=(F[k-1]-1) + (F[k-2]-1)+1。说明只要顺序表的长度为F[k]-1,则可以-将顺序表分成长度为F[k-1]-1和F[k-2]-1的两段,即中间位置为:mid=low+F[k-1]-1。
  • 类似的每个字段也可以用相同的方式进行分割。
  • 可能顺序表长度n不一定等于F[k]-1,需要将原来的顺序表长度n增加至F[k]-1。(k值只要使得F[k]-1大于或等于n)。
/**
 * @author blog.unclezs.com
 * @date 2020/7/31 19:00
 */
public class FibonacciSearch {
    public static void main(String[] args) {
        int[] array = {1, 8, 10, 89, 1000, 1234};
        int index = fibonacciSearch(array, 1);
        if(-1 == index) {
            System.err.println("没有找到");
        } else {
            System.out.println("找到,位置:" + index);
        }
    }

    /**
     * 斐波那契查找
     */
    public static int fibonacciSearch(int[] array, int key) {
        int length = array.length;
        int low = 0;
        int high = length - 1;
        // 斐波那契分割数的索引
        int k = 0;
        int mid = 0;
        // 找到有序表元素个数在斐波那契数列中最接近的最大数列值
        while(high > (fibonacci(k) - 1)) {
            k++;
        }
        // 补齐有序表
        int [] tmpArray = Arrays.copyOf(array, fibonacci(k));
        for(int i = length; i < tmpArray.length; i++) {
            tmpArray[i] = array[high];
        }
        while(low <= high) {
            mid = low + fibonacci(k - 1) - 1;
            // 查找值小于中值,在小的那一部分继续查找
            if(key < tmpArray[mid]) {
                high = mid - 1;
                k--;
            }
            // 查找值大于中值,在大的那一部分继续查找
            else if(key > tmpArray[mid]) {
                low = mid + 1;
                k -= 2;
            } else {
                // 可能存在补齐列表
                return Math.min(mid, high);
            }
        }
        return -1;
    }
    /**
     * 动态规划实现斐波那契数列
     *
     * @param n /
     * @return /
     */
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        int pre1 = 0;
        int pre2 = 1;
        int total = pre1 + pre2;
        for (int i = 2; i <= n; i++) {
            total = pre1 + pre2;
            pre1 = pre2;
            pre2 = total;
        }
        return total;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

# 树表查找

# 二叉查找树

二叉查找树是先对待查找的数据进行生成树,确保树的左分支的值小于右分支的值,然后在就行和每个节点的父节点比较大小,查找最适合的范围。 这个算法的查找效率很高,但是如果使用这种查找方法要首先创建树。

对二叉查找树进行中序遍历即可得到一个有序的列表。

对这个方面还有升级版本的红黑树,来保证平衡

# 平衡查找树之2-3查找树(2-3 Tree)

和二叉树不一样,2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node),他保存1个key和左右两个自己点。对应3节点(3-node),保存两个Key。

2-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还要大。

# 分块查找

分块查找又称索引顺序查找,它是顺序查找的一种改进方法。

算法思想:将n个数据元素"按块有序"划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须"按块有序";即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,……

算法流程:

  1. 先选取各块中的最大关键字构成一个索引表;
  2. 查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。

# 哈希查找

我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数, 也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素"分类",然后将这个元素存储在相应"类"所对应的地方。但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了"冲突",换句话说,就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。

总的来说,"直接定址"与"解决冲突"是哈希表的两大特点。

在 GitHub 编辑此页 (opens new window)
上次更新: 2024/02/25, 12:11:11
TCP的三次握手与四次挥手
常用排序算法及Java实现

← TCP的三次握手与四次挥手 常用排序算法及Java实现→

Theme by Vdoing | Copyright © 2018-2024 unclezs
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式