数据结构--查找算法Java

本文主要是介绍数据结构--查找算法Java，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

顺序表查找（线性查找）

时间复杂度：O(n)
遍历

有序表查找

a.折半查找（二分法）
时间复杂度：O(logn)

    public int search(int[] nums, int target) {
        if(nums.length == 0)
        {
            return 0;
        }
        int low = 0;
        int high = nums.length - 1;
        int mid = 0;
        while(low <= high)
        {
            mid = (low + high) / 2;
            if(nums[mid]  == target)
            {                
                return mid;
            }
            else if(nums[mid] > target)
            {
                high = mid - 1;
            }
            else{
                low = mid+1;
            }
        }
        return mid;
    }

b.插值查找
时间复杂度：O(logn)
将mid修改为

mid = low + (high - low) * (target - nums[low])/(nums[high] - nums[low]);

c.斐波那契查找
时间复杂度：O(logn)
1 1 2 3 5 8 13 21 34 55 89…
使用斐波那契数列来估计mid

线性索引查找

稠密索引、分块索引、倒排索引

二叉排序树（二叉查找树）

若它的左/右子树不为空，则左/右子树上所有结点的值均小于/大于它的根节点值，它的左右子树也分别为二叉排序树。
时间复杂度：O(logn) ~ O(n)

平衡二叉树（AVL树）

AVL树：左子树和右子树的高度至多差1
将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF，BF的绝对值若大于1，则二叉树是不平衡的。
时间复杂度：O(logn)

多路查找树（B树）

a.2-3树
每个结点有2个孩子或3个孩子，叶子都在同一层次有序

b.2-3-4树
2结点，3结点，4结点

c.B树
B树是一种平衡的多路查找树，结点最大的孩子数目称为B树的阶。

d.B+树

1. 二叉查找树(BST)：解决了排序的基本问题，但是由于无法保证平衡，可能退化为链表；
2. 平衡二叉树(AVL)：通过旋转解决了平衡的问题，但是旋转操作效率太低；
3. 红黑树：通过舍弃严格的平衡和引入红黑节点，解决了AVL旋转效率过低的问题，但是在磁盘等场景下，树仍然太高，IO次数太多；
4. B树：通过将二叉树改为多路平衡查找树，解决了树过高的问题；
5. B+树：在B树的基础上，将非叶节点改造为不存储数据的纯索引节点，进一步降低了树的高度；此外将叶节点使用指针连接成链表，范围查询更加高效。
   添加链接描述

散列表查找（哈希表）

查找步骤：1.存储时，通过散列函数计算出记录的散列地址；2.查找记录时，通过同样的散列函数计算记录的散列地址，并按此地址访问该记录。
散列技术既是一种存储方法，也是一种查找方法。
时间复杂度：O(1) ~ O(n)
a.散列函数的构造方法
（1）直接定址法（2）数字分析法（3）平方取中法（4）折叠法（5）除留余数法（6）随机数法
b.处理散列冲突
（1）开放定址法（2）再散列函数法（3）链地址法（4）公共溢出区：基本表，溢出表

这篇关于数据结构--查找算法Java的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！