Please enable Javascript to view the contents

Java算法及其应用

 ·  ☕ 6 分钟  ·  🎅 qqnv
    🏷️

常见算法

查找算法（7种）

  • 基本查找
  • 二分/折半查找
  • 分块查找
  • 插值查找（数据分布比较均匀，否则反而效率更差） mid = min + (key-arr[min]) / (arr[max]-min) * (max-min)
  • 斐波那契查找 mid = min + 黄金分割点左半边长度 - 1 注：黄金比例为1:0.618
  • 树表查找
  • 哈希查找

基本查找

核心：从0索引开始挨个往后查找

1
2
3
4
5
6
7
8

public static boolean basicSearch(int[] arr ,int number){
	for(int i = 0; i < arr.length; i++){
		if(arr[i] == number){
			return true;
		}
	}
	return false;
}

（折半/二分）查找

前提条件：数组中的数据必须是有序的

核心逻辑：每次排除一半的查找范围

  1. min和max表示当前要查找的范围
  2. mid是在min和max中间
  3. 如果要查找的元素在mid左边，缩小范围时，min不变，max等于mid减1
  4. 如果要查找的元素在mid右边，缩小范围时，max不变，min等于mid加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

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {7,23,79,81,97,123,145,168,179,191};
        int i = binarySearch(arr, 168);
        System.out.println(i);
    }

    /**
     *
     * @param arr
     * @param number
     * @return
     */
    public static int binarySearch(int[] arr, int number){
        int min = 0;
        int max = arr.length -1;
        while(true){
            if(min > max){
                return -1;
            }
            int mid = (min + max)/2;
            if(arr[mid] > number){
                max = mid - 1;
            }else if(arr[mid] < number){
                min = mid + 1;
            }else {
                return mid;
            }
        }
    }
}

分块查找

分块原则1: 前一块中的最大数据，小于后一块中的所有数据（块内无序，快间有序）

分块的原则2: 快数数量一般等于数字的个数开根号

核心思路：先确定要查找的元素在哪一块，然后在块内挨个查找

 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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

public class BinaryBlockedSearch {
    public static void main(String[] args) {
        int[] arr = {16,5,9,12,21,18,
                32,23,37,26,45,34,
                50,48,62,52,73,66};
        //创建三个块的对象
        Block b1 = new Block(21, 0, 5);
        Block b2 = new Block(45, 6, 11);
        Block b3 = new Block(73, 12, 17);
        //定义数组管理三个块的对象
        Block[] blocks = {b1, b2, b3};
        //定义一个变量来记录要查找的元素
        int number = 73;
        //查找
        int index = getIndex(arr,blocks,number);
        System.out.println(index);
    }

    /**
     * 分块查找逻辑
     * @param arr
     * @param blocks
     * @param number
     * @return
     */
    private static int getIndex(int[] arr, Block[] blocks, int number) {
        int indexBlock = findIndexBlock(blocks,number);
        if (indexBlock == -1){
            return -1;
        }
        //获取这一块的起始索引和结束索引
        int startIndex = blocks[indexBlock].getStartIndex();
        int endIndex = blocks[indexBlock].getEndIndex();
        for (int i = startIndex; i <= endIndex; i++) {
            if (arr[i] == number){
                return i;
            }
        }
        return -1;
    }

    /**
     * 确定number在哪个块中
     * @param blocks
     * @param number
     * @return
     */
    private static int findIndexBlock(Block[] blocks, int number) {
        //从0索引开始遍历blocks，如果number小于max，那么就表示number在这一块当中
        for (int i = 0; i < blocks.length; i++) {
            if (number <= blocks[i].getMax()){
                return i;
            }
        }
        return -1;
    }


}
class Block{
    private int max;
    private int startIndex;
    private int endIndex;

    public Block() {
    }

    public Block(int max, int startIndex, int endIndex) {
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    public int getMax() {
        return max;
    }

    public void setMax(int max) {
        this.max = max;
    }

    public int getStartIndex() {
        return startIndex;
    }

    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    public int getEndIndex() {
        return endIndex;
    }

    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }
}

排序算法（10种）

  • 冒泡排序
  • 选择排序
  • 插入排序
  • 快速排序
  • 希尔排序
  • 归并排序
  • 堆排序
  • 计数排序
  • 桶排序
  • 基数排序

冒泡排序

  1. 相邻的数据两两比较，小的放前面，大的放后面

  2. 第一轮比较完毕之后，最大值已确定，第二轮可以少循环一次，后面以此类推

  3. 如果数组中有n个数据，总共需执行n-1轮代码

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

    public class BubbleSort {
    public static void main(String[] args) {
        //定义数组
        int[] arr = {2, 4, 5, 3, 1};
        for (int j = arr.length - 1; j > 0; j--) {
            for (int i = 0; i < j; i++) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }
        Tool.printIntArr(arr);
    }
}

选择排序

原理：从0索引开始，拿着每一个索引上的元素跟后面的元素依次比较，小的放前面，大的放后面，以此类推

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public class SelectSort {
    public static void main(String[] args) {
        //定义数组
        int[] arr = {2, 4, 5, 3, 1};

        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        Tool.printIntArr(arr);
    }
}

插入排序

原理：将数组分为有序和无序两组，遍历无序数据，将元素插入有序序列中即可

将0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一个当成是无序的。遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。
N的范围：0～最大索引

 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

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        //1.找到无序数组是从哪个索引开始的
        int startIndex = -1;
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                startIndex = i + 1;
                break;
            }
        }
        //2.遍历从startIndex开始到最后一个元素，依次得到无序数组中的每一个元素
        for (int i = startIndex; i < arr.length; i++) {
            //记录当前要插入数据的索引
            int j = i;
            while (j > 0 && arr[j] < arr[j-1]) {
                //交换位置
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                j--;
            }
        }
        Tool.printIntArr(arr);
    }
}

快速排序

原理：

  • 将排序范围中的第一个数字作为基准数，再定义两个变量start，end
  • start从前往后找比基准数大的，end从后往前找比基准数小的
  • 找到之后交换start和end指向的元素，并循环这一过程，直到start和end处于同一个位置，该位置是基准数在数组中应存入的位置，再让基准数归位
  • 归位后的效果：基准数左边的比基准数小，基准数右边的比基准数大

第一轮：把0索引的数字作为基数，确定基准数在数组中正确的位置
比基准数小的全部在左边，比基准数大的全部在右边

 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

public class QuickSort {
    public static void main(String[] args) {
//        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        int[] arr = new int[100000];
        Random r = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt();
        }
        long start = System.currentTimeMillis();
        quickSort(arr, 0, arr.length - 1);
        long end = System.currentTimeMillis();
        Tool.printIntArr(arr);
        System.out.println(end - start);
    }

    public static void quickSort(int[] arr, int i, int j) {
        //定义两个变量记录查找的范围
        int start = i;
        int end = j;

        //递归的出口
        if (start > end) return;

        //记录基准数
        int baseNumber = arr[i];
        while (start != end) {
            //利用end，从后往前开始找，找比基准数小的数字
            while (true) {
                if (end <= start || arr[end] < baseNumber) break;
                end--;
            }
            //利用start，从前往后找，找比基准数大的数字
            while (true) {
                if (end <= start || arr[start] > baseNumber) break;
                start++;
            }
            //把end和start指定的元素进行交换
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }

        //start和end指向了同一个元素的时候，那么循环就会结束
        //表示已经找到了基准数在数组中应存入的位置
        //基准数归位，就是拿着这个范围内的第一数字，跟start指向的元素进行交换
        int temp = arr[i];
        arr[i] = arr[start];
        arr[start] = temp;

        //确定6左边的范围，重复刚才所做的事情
        quickSort(arr, i, start - 1);
        //确定6左边的范围，重复刚才所做的事情
        quickSort(arr, start + 1, j);
    }
}

递归

定义：递归指的是方法中调用方法本身的现象

作用：把一个复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解

 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

public class Recursion {
    public static void main(String[] args) {
//        System.out.println(getSum(100));
        System.out.println(getFactorial(5));
    }

    /**
     * 递归求和
     *
     * @param number
     * @return
     */
    public static int getSum(int number) {
        if (number == 1) return 1;
        return number + getSum(number - 1);
    }

    /**
     * 求阶乘
     * @param number
     * @return
     */
    public static int getFactorial(int number) {
        if (number == 1) return 1;
        return number * getFactorial(number - 1);
    }
}

字符串匹配算法

基本查找

KMP算法

分享
qqnv
作者
qqnv
Android Developer

相关内容