数据结构Java版的查找算法实现

超、凢脫俗 2022-06-10 10:05 175阅读 0赞

import java.util.Arrays;
    import java.util.HashMap;
    import java.util.Iterator;
    import java.util.Set;
    
    /**
     * 查找的基本算法:
     *                                         - 顺下查找
     *            -基于线性表的查找（静态查找）- 折半查找
     *            -                            - 分块查找
     *            -
     * 比较式查找 -
     *            -                            - 二叉排序树（B树）
     *            -                            - 平衡二叉树
     *            -基于树的查找（动态查找）
     *            -                            - B- 树
     *            -                            - B+ 树
     * 计算式查找 -  -  - -  -  -              - Hash查找
     *
     *  2017/8/8.
     */
    public class SearchMethod {
        public static void main(String[] agrs){
            int[] num = new int[]{7,9,10,8,2,1,3,4,6,5,20,25,56,0,13,14,15};
    //        System.out.println(OrderSearch(num,2));
    //        System.out.println(BinarSearch(num,2));
    //        int index = BlockSearch(num,SplitBlock(num,3),0);
    //        System.out.println(index);
              //构建二叉排序树
    //        BinarySortTree b = new BinarySortTree();
    //        b.val = 5;
    //        b.left_child = new BinarySortTree();
    //        b.right_child = new BinarySortTree();
    //        b.left_child.val = 3;
    //        b.right_child.val = 7;
    //        b.left_child.left_child = new BinarySortTree();
    //        b.left_child.right_child = new BinarySortTree();
    //        b.left_child.left_child.val = 2;
    //        b.left_child.right_child.val = 4;
    //        b.right_child.left_child = new BinarySortTree();
    //        b.right_child.right_child = new BinarySortTree();
    //        b.right_child.left_child.val = 6;
    //        b.right_child.right_child.val = 8;
    //        SearchMethod search = new SearchMethod();
    //        System.out.println(search.BinaryTreeSearch(b,9));
    
    
        }
    
        /** 1
         * 顺序查找:逐个比较，直到找到或者查找失败。
         * 时间复杂度可以表示O(h)=O(n)
         * 空间复杂度：S(n) = O(n)
         * @param num 查找的数组
         * @param n 查找的数
         * @return 返回下标
         */
        public static int OrderSearch(int[] num,int n){
            for (int i = 0; i < num.length - 1; i++) {
                if (num[i] == n){
                    return i;
                }
            }
            return -1;
    
        }
    
        /** 2
         * 二分法查找:对于已经按照一定顺序排列好的列表，
         * 每次都用关键字和中间的元素对比，然后判断是在前部分还是后部分还是就是中间的元素，
         * 然后继续用关键字和中间的元素对比。
         * 时间复杂度可以表示O(h)=O(log2n)
         * @param num 查找的数组
         * @param n 查找的数
         * @return 返回下标
         */
        public static int BinarSearch(int[] num,int n){
            int low = 0;
            int high = num.length - 1;
            while (low <= high){
                int mid = (low+high)/2;
                int tem = num[mid];
                if (tem < n){
                    low = mid + 1;
                }else if (tem > n){
                    high = mid - 1;
                }else {
                    return mid;
                }
            }
            return -1;
        }
    
        /**
         * 分块查找的分块：0<可分块<=查找数组元素和
         * 采用Hashmap保存区块的极值和起始下标
         * @param num 查找数组
         * @param n 分块个数
         * @return 返回分块起始下标和块的最大值
         */
        public static HashMap<Integer,Integer> SplitBlock(int[] num,int n){
            HashMap<Integer,Integer> block = new HashMap<>();
            int tem = num[0];
            for (int i = 0; i < num.length - 1; i++) {
                if (i % n == 0){ //起始分块
                    if ((i+n) >= num.length-1){ //判断是否是最后一个区块 最后一个区块元素可能小于或大于前面区块元素
                        for (int j = i; j < num.length; j++) { //区块内查找极值
                            if (num[j] > tem){
                                tem = num[j];
                            }
                        }
                        //保存区块极值和起始下标
                        block.put(tem,i);
                    }else {
                        for (int j = i; j < i+n; j++) { //区块内查找极值
                            if (num[j] > tem){
                                tem = num[j];
                            }
                        }
                        //保存区块极值和起始下标
                        block.put(tem,i);
                        //初始化区块比较值
                        tem = num[i+n-1];
                    }
                }
            }
            return block;
        }
    
        /**
         * 分块查找：可查找任意无排序的数组
         * step1 先选取各块中的最大关键字构成一个索引表
         * step2 查找分两个部分：先对索引表进行二分查找或 顺序查找，然后在确定的块中顺序查找。
         * ASLbs=(n/s+s)/2  +1,（其中s是每块的元素个数，n为表长）
         * 时间复杂度为O(n)~O(log2n)
         * @param num
         * @param index
         * @param n
         * @return
         */
        public static int BlockSearch(int[] num,HashMap<Integer,Integer> index,int n){
            //获取索引极值进行排序
            Iterator<Integer> ite = index.keySet().iterator();
            int[] index1 = new int[index.size()];
            int i = 0;
            while (ite.hasNext()){
                index1[i++] = ite.next();
            }
            //索引极值从小到大排序
            Arrays.sort(index1);
            //查找元素所在区块
            for (int j = 0; j < index1.length; j++) {
                if (n <= index1[j]){ //小于索引值说明在此区块内进行查找
                    int start = index.get(index1[j]);
                    int end = 0;
                    if (j != index1.length -1){
                        end = index.get(index1[j+1]);
                    }else {
                        end = num.length;
                    }
                    //查找区块元素位置
                    for (int k = start; k < end; k++) {
                            if (n == num[k]){
                                return k;
                            }
                    }
                }
            }
            return -1;
        }
    
        /**
         * 二叉排序树/B树查找
         * 时间复杂度：O(logn)
         * @param b 二叉排序树
         * @param n 查找值
         * @return 返回结果
         */
       public int BinaryTreeSearch(BinarySortTree b,int n){
           if (b != null){
               if (b.val == n){
                   return 1;
               }else if (b.val > n){
                   return BinaryTreeSearch(b.left_child,n);
               }else if (b.val < n){
                   return BinaryTreeSearch(b.right_child,n);
               }
           }
           return -1;
       }
       //平衡二叉树：且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
        //最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1
        //查找与二叉排序树一样
    }