java选择算法、java查找算法汇总

àì夳堔傛蜴生んèń 2022-07-12 02:12 106阅读 0赞

### 文章目录 ###

*  线性查找
 *  二分查找算法
 *   *  非递归写法
     *  递归写法
 *  分块查找
 *  二叉树查找

# 线性查找 #

顺序查找适合于存储结构为顺序存储或链接存储的线性表

public static int query(int[] arrays, int target){
        for(int i = 0 ;i < arrays.length ; i ++){
            if(arrays[i] == target)return i;
        }
        return -1;//没找到
    }

线性查找是性能最差的查找算法，时间复杂度： `O(N)`

# 二分查找算法 #

**`二分查找要求数组为有序数组`**。 时间复杂度： `O（logN）`。

## 非递归写法 ##

public static int query(int[] arrays, int target){ 
    
            int begin = 0, end = arrays.length-1, mid = (begin + end) / 2;
    
            while(end >= begin){ 
                if(arrays[mid] == target)return mid;
                else if(arrays[mid] > target) end = mid - 1;
                else begin = mid + 1;
                mid = (begin + end) / 2;
            }
    
            return -1;//没找到
        }

## 递归写法 ##

public static int query(int[] arrays, int target, int begin, int end){ 
    
            if(begin > end) return -1;//没找到
            int mid = (begin + end) / 2;
    
            if(arrays[mid] == target) return mid;
            else if(arrays[mid] > target) return query(arrays, target, begin, mid - 1);
            else return query(arrays, target, mid + 1, end);
        }
        public static void main(String[] args){ 
            //一个有序数组
            int[] arrays = { 1,3,5,6,7,9,12,50};
            int index = query(arrays, -9, 0, arrays.length - 1);
            System.out.println(index);
        }

# 分块查找 #

先建立一个索引表，索引表中对当前待查的元素进行了分块处理，每一块中包含了当前块中的最大元素，并且后一块中的元素全部大于之前元素，块的个数一般都是平均分割的。这样当查询某一元素的时候只需要先确定属于哪一个块，之后再到块中进行查找定位，他的效率是基于顺序查找和折半查找中间的，并且他比折半查找要更加灵活，不在局限于有顺序表的这一套路中了。  
![这里写图片描述][SouthEast]

# 二叉树查找 #

二叉树查找是现将要查找的数组生成二叉排序树。具体参考博主的另一篇文章 [java操作二叉树：构建二叉树；前序、中序、后续、层次遍历][java]

[SouthEast]: /images/20220711/392fbc5788d54c069939b5480bf5f0e3.png
[java]: http://blog.csdn.net/liubenlong007/article/details/54972770