常见查找算法(Java实现)

zebulonsu 2018-05-09

展开全文

查找的性能分析：

对于查找算法而言，常用“其关键字和给定值进行过比较的记录个数的平均值”作为衡量查找算法的依据。

定义：为了确定记录在查找表中的位置，需要和给定的值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。
对于含有n个记录的表。查找成功时的平均查找长度为

A S L = \sum_{i = 1}^{n} P_{i} C_{i}

其中

P_{i}

为查找表中第

i

个记录的概率，且

\sum_{i = 1}^{n} P_{i} = 1

C_{i}

为找到表中关键字与给定值相等的第i个记录时，和给定值已经进行过比较的关键字个数。

静态表查找

顺序查找：

算法描述：从表中的第一个或者是最后一个记录开始，逐个的将表中记录的关键字和给定值进行比较。若某个记录的关键字和给定值相等，则查找成功；若表中所有记录的关键字和给定值都不相等，则查找失败。
算法实现：

public class OrderSearch {

    public static void main(String[] args) {
        int[] table = {1,23,4,5,6};
        System.out.println(OrderSearch.orderSearch(table, 5));

    }


    /**
     * 顺序查找
     * @param table
     * @param keyWord
     * @return
     */
    public static boolean orderSearch(int[] table,int keyWord){
        for(int i = 0;i<table.length;i++){
            if(table[i] == keyWord){
                return true;
            }
        }
        return false;
    }

}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

折半查找（针对有序序列）：

算法描述：折半查找的前提条件是在一个有序的序列中。首先确定待查记录所在的区间，然后逐步的缩小范围区间直到找到或者找不到该记录为止。与数学中的二分法一样。
算法实现：

public class BinarySearch {

    public static void main(String[] args) {
        int[] table = {2,4,5,6,7,8,9,10};
        System.out.println(BinarySearch.binarySearch(table, 20));

    }

    public static boolean binarySearch(int[] table ,int keyWord){
        int low = 0;
        int height = table.length-1;
        int mid;
        while(low<=height){
            mid = (low+height)/2;
            if(table[mid]> keyWord){
                height = mid-1;
            }else if(table[mid]<keyWord){
                low = mid+1;
            }else if(table[mid] == keyWord){
                return true;
            }
        }
        return false;
    }

}
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

斐波那契查找（针对有序序列）：

算法描述：斐波那契查找是根据斐波那契序列的特点对表进行分割。假设表中记录的个数比某个斐波那契数小1，即 $n = F_{n} - 1$ ，然后将给定值和表中第 $F_{n - 1}$ 个记录的关键字进行比较。若相等，则查找成功；若给定关键字 $<$ 表中第 $F_{n - 1}$ 个记录的关键字，则继续在表中从第一个记录到第 $F_{n - 1} - 1$ 个记录之间查找；若给定关键字 $>$ 表中第 $F_{n - 1}$ 个记录的关键字，则继续在自 $F_{n - 1} + 1$ 至 $F_{n} - 1$ 的子表中查找。
算法实现：

public class FibonacciSearch {

    public static void main(String[] args) {
        int[] table = {1,2,3,4,5,6,7,8,9,10,11,12,13,14};
        for(int i = 0;i<table.length;i++){
            System.out.println("表中记录为"+table[i]+"\t,查询结果为"+FibonacciSearch.fibonacciSearch(table, table[i])+"\n");
        }

        for(int i = 0;i<5;i++){
            int ran = new Random().nextInt(100)+14;
            System.out.println("关键字为："+ran+"查询结果为"+FibonacciSearch.fibonacciSearch(table, ran)+"\n");
        }

    }

    public static boolean fibonacciSearch(int[] table,int keyWord){
        //确定需要的斐波那契数
        int i = 0;
        while(getFibonacci(i)-1 == table.length){
            i++;
        }
        //开始查找
        int low = 0;
        int height = table.length-1;
        while(low<=height){
            int mid = low + getFibonacci(i-1);
            if(table[mid] == keyWord){
                return true;
            }else if(table[mid]>keyWord){
                height = mid-1;
                i--;
            }else if(table[mid]<keyWord){
                low = mid+1;
                i-=2;
            }
        }
        return false;
    }

    /**
     * 得到第n个斐波那契数
     * @return
     */
    public static int getFibonacci(int n){
        int res = 0;
        if(n == 0){
            res = 0;
        }else if(n == 1){
            res = 1;
        }else{
            int first = 0;
            int second = 1;
            for(int i = 2;i<=n;i++){
                res = first+second;
                first = second;
                second = res;
            }
        }
        return res;
    }
}
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