查找

  1. 基本查找
  2. 二分查找/折半查找
  3. 分块查找
  4. 插值查找
  5. 斐波那契查找
  6. 树表查找
  7. 哈希查找

基本查找

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void main(String[] args) {
    // 需求：定义一个方法利用基本查找，查询某个元素是否存在
    // 数据如下：{131,127,147,81,103,23,7,79}
    int[] arr = new int[]{131,127,147,81,103,23,7,79};
    boolean res = basicSearch(arr,100);
    System.out.println(res);
}

public static Boolean basicSearch(int[] arr,int number) {
    // 利用基本查找来查找number是否存在
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == number) {
            return true;
        }
    }
    return false;
}

二分查找

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

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

优势：提高查找效率

假设有一个数组为：[7, 23, 79, 81, 103, 127, 131, 147]

那么，可以得到两个值，min=0，max=7，这两个值表示最大索引值和最小索引值，

接着 (max + min) / 2，得出来的值就是mid值

  • 如果查找的元素在mid的左边，缩小范围时，min不变，max等于mid减1
  • 如果查找的元素在mid的右边，缩小范围时，max不变，min等于mid加1
  • 如果 min 大于 max 时，说明数据不存在

如果数据是乱的，先排序再用二分查找得到的索引没有实际意义，只能确定当前数字在数组中是否存在，因为排序之后数字的位置就可能发生变化了（排序浪费的性能比查找高得多）

插值查找（二分查找改进）

假设，数组的数据都是均匀分布的，如[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，那么可以套用以下公式

1
mid = min + ((key-arr[min]) / (arr[max]-arr[min])) * (max-min)

通过以上公式，可以获得目标数据在索引中的大概位置

缺点也很明显：需要数据均匀分布，若是不均匀的则会导致资源浪费或查找不到

斐波那契查找（二分查找改进）

斐波那契查找就是在二分查找的基础上，根据斐波那契数列进行分割的

斐波那契数列：

1
[F0, F1, F2, F3, F4, F5, F6, F7, F8, F9, F10]
1
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

首先，将要查找的数组长度看为 F(k)，mid的左侧看作 F(k-1)-1，mid的右侧看作 F(k-2)

可以得出：F(k)=F(k-1)-1+F(k-2)

1
mid = arr[min] + F(k-1) - 1

解释：
在斐波那契数列找一个等于略大于查找表中元素个数的数f(n)，将原查找表扩展为长度F(n)（如果要补充元素，则补充重复最后一个元素，直到满足F(n)），完成后进行斐波那契分割，即F(n)个元素分割为前半部分F(n-1)个元素，后半部分F(n-2)个元素，找出要查找的元素在哪一部分并递归，直到找到

  • 相等，则mid位置的元素即为所求

  • >，则low=mid+1，k-=2

    解释：low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2说明范围[mid+1,high]内的元素个数为

    n-(F(k-1)) = Fk-1-F(k-1) = Fk-F(k-1)-1=F(k-2)-1

  • <，则high=mid-1，k-=1

分块查找

假设有这样一个无序的数组：

[7, 10, 13, 19, 16, 20, 27, 22, 30, 40, 36, 43, 50, 48]

把这个数组分成几个不同的块，变成：

[7,10][13,19,16,20][27,22,30,40,36][43,50,48]

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

分块原则2：块数数量一般等于数字的个数开根号。比如：16个数字一般分为4块左右

排序

冒泡排序

冒泡排序：

  1. 相邻的数据两两比较，小的放前面，大的放后面
  2. 第一轮循环结束，最大值已经找到，在数组的最右边
  3. 第二轮循环，只需要找剩余数组的最大值
  4. 以此类推，如果数组中有n个数据，总共只要执行n-1轮的代码就可以
1
2
3
4
5
6
7
8
9
10
11
12
13
int[] arr = {2,4,5,3,1};

// 外层循环代表需要执行几轮对比
for (int i = 0; i < arr.length - 1; i++) {
    // 内层代表索引为0的数据逐一往后对比
    for (int j = 0; j < arr.length - 1 - i; j++) {
        if(arr[j] > arr[j+1]){
            int tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1]=tmp;
        }
    }
}

选择排序

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

1
2
3
4
5
6
7
8
9
10
int[] arr = {2,4,5,3,1};
for (int i = 0; i < arr.length; i++) {
    for (int j = i+1; j < arr.length; j++) {
        if (arr[i] > arr[j]) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
}

插入排序

插入排序：将0索引的元素到N索引的元素看作是有序的，把N+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
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; i++) {
    if(arr[i] > arr[i+1]) {
        // 确定无序数组开始索引
        startIndex = i + 1;
        break;
    }
}

// 2. 遍历从startIndex开始到最后一个元素，依次得到无序的那一组数据中的每一个元素
for (int i = startIndex; i < arr.length; i++) {
    // System.out.print(arr[i] + " ");
    // 将遍历到的数组，插入到前面有序的这一组当中

    // 1. 记录当前要插入数据的索引
    int j = i;

    // 2. 从后往前开始排序
    while (j > 0 && arr[j] < arr[j - 1]) {
        int tmp = arr[j];
        arr[j] = arr[j-1];
        arr[j-1] = tmp;
        j--;
    }
}

目前的排序的方法，速度对比：选择排序 > 插入排序 > 冒泡排序

如果数组本身不是很乱的，如 [2,5,12,43,23,11,65] 这种，插入排序是最快的

递归算法

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

递归的注意点：递归一定要有出口，否则就会出现内存溢出

递归算法的作用

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

递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算

书写递归的两个核心

  • 找出口：什么时候不再调用方法
  • 找规则：如何把大问题变成规模较小的问题

快速排序

第一轮：把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
public static void quickSort(int[] arr,int i,int j) {
    // 定义两个变量记录要查找的范围
    int start = i + 1;
    int end = j;

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

    int baseNumber = arr[i];
    while (start != end) {
        // 利用end，从后往前找，找比基准数小的数字
        
       // 这里的 end 和 start 两个循环不能交换位置，否则会导致基准数归位的位置不正
        while (true) {
            if (end <= start || arr[end] < baseNumber) {
                break;
            }
            end--;
        }

        // 利用start，从前往后找，找比基准数大的数字
        while (true) {
            if (end <= start || arr[start] > baseNumber) {
                break;
            }
            start++;
        }

        // 把end和start指向的元素进行交换
        int tmp = arr[start];
        arr[start] = arr[end];
        arr[end] = tmp;
    }

    // 当 start 和 end 指向了同一个数字，那么上面的循环就会结束
    // 表示已经找到了基准数在数组中应存入的位置
    // 基准数归位
    int tmp = arr[i];
    arr[i] = arr[start];
    arr[start] = tmp;

    // 确定基准数左边的范围和基准数右边的范围
    quickSort(arr,i,start - 1);
    quickSort(arr,start + 1,j);
}

总结

  1. 冒泡排序：

    相邻的元素两两比较，小的放前面，大的放后面

  2. 选择排序：

    从0索引开始，拿着每一个索引上的元素跟后面的元素依次比较

    小的放前面，大的放后面，以此类推

  3. 插入排序：

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

  4. 快速排序：

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

Arrays

操作数组的工具类

方法名 说明
public static String toString(数组) 把数组拼接成一个字符串
public static int binarySearch(数组, 查找元素) 二分查找法找元素
public static int[] copyOf(原数组, 新数组长度) 拷贝数组
public static int[] copyOfRange(原数组, 起始索引, 结束索引) 拷贝数组（指定范围）
public static void fill(数组, 元素) 填充数组
public static void sort(数组) 按照默认方式进行数组排序
public static void sort(数组, 排序规则) 按照指定的规则排序 
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
// toString 把数组变为字符串
System.out.println("------- toString -------");
int[] arr = {1,2,3,4,5,6,7,8,9,10};
System.out.println(Arrays.toString(arr));

// binarySearch：二分查找法查找元素
// 注意：需要查找的数组必须是升序的
// 如果数据不存在，则返回数据应该所在位置的 - 索引 - 1
System.out.println("------- binarySearch -------");
System.out.println(Arrays.binarySearch(arr,5));
System.out.println(Arrays.binarySearch(arr,10));
System.out.println(Arrays.binarySearch(arr,15));

// copyOf：拷贝数组
System.out.println("------- copyOf -------");
int[] newArr1 = Arrays.copyOf(arr,20);
System.out.println(Arrays.toString(newArr1));

// copyOfRange：指定拷贝数组的范围
// 细节：包头不包尾
System.out.println("------- copyOfRange -------");
int[] newArr2 = Arrays.copyOfRange(arr,0,9);
System.out.println(Arrays.toString(newArr2));

// fill：填充数组
System.out.println("------- fill -------");
Arrays.fill(arr,100);
System.out.println(Arrays.toString(arr));

// sort：排序，默认情况下，给基本数据类型进行升序排序
System.out.println("------- sort -------");
int[] arr2 = {10,2,3,5,6,1,7,8,4,9};
Arrays.sort(arr2);
System.out.println(Arrays.toString(arr2));
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
Integer[] arr={2,3,1,5,6,7,8,4,9};

// 第二个参数，是一个接口，所以在调用方法的时候，需要传递这个接口的实现类对象，作为排序规则
// 但是这个实现类，只要用一次，所以就没有必要单独的去写一个类，直接采取匿名内部类的方式就可以了
Arrays.sort(arr, new Comparator<Integer>() {
    // 底层原理：
    // 利用插入排序 + 二分查找的方式进行排序的
    // 默认把0索引的数据当作是有序的序列，1索引到最后认为是无序的序列
    // 遍历无序的序列得到里面的每一个元素，假设当前遍历得到的元素是A元素
    // 把A往有序序列中进行插入，在插入的时候，是利用二分查找确定A元素的插入点
    // 拿着A元素，跟插入点的元素进行比较，比较的规则就是compare方法的方法体
    // 如果方法的返回值是负数，拿着A继续跟前面的数据进行比较
    // 如果方法的返回值是正数，拿着A继续跟后面的数据进行比较
    // 如果方法的返回值是0，也拿着A跟后面的数据进行比较
    // 直到能确定A的最终位置为止

    // compare的形参：
    // o1：表示在无序序列中遍历得到的每一个元素
    // o2：表示在有序序列中的元素

    // 返回值：
    // 负数：表示当前要插入的元素，是小的，要放在前面
    // 正数：表示当前要插入的元素，是大的，要放在后面
    // 0：表示当前要插入的元素跟现在的元素比是一样的，也会放在后面

    // 简单理解：
    // o1 - o2 升序排列
    // o2 - o1 降序排列
    @Override
    // Integer[] arr={2,3,1,5,6,7,8,4,9};
    public int compare(Integer o1, Integer o2) {
        System.out.println("==========");
        System.out.println("o1：" + o1);
        System.out.println("o2：" + o2);
        return o1 - o2;
    }
});

System.out.println(Arrays.toString(arr));

Lambda表达式

对 Arrary.sort() 进行简化：

1
2
3
4
5
6
Integer[] arr={2,3,1,5,6,7,8,4,9};
Arrays.sort(arr, (Integer o1,Integer o2) -> {
    return o1 - o2;
});

System.out.println(Arrays.toString(arr));

函数式编程

函数式编程（Functional programming）是一种思想特点

面向对象：先找对象，让对象做事情

函数式编程思想，忽略面向对象的复杂语法，强调做什么，而不是谁去做

而Lambda表达式就是函数式思想的体现

Lambda表达式的标准格式

Lambda表达式是JDK8开始后的一种新语法形式

1
() -> {}
  • () 对应着方法的形参
  • -> 固定格式
  • {}对应着方法的方法体

注意点：

  • Lambda表达式可以用来简化匿名内部类的书写

  • Lambda表达式只能简化函数式接口的匿名内部类的写法

  • 函数式接口：

    有且仅有一个抽象方法的接口叫做函数式接口，接口上方可以加@FunctionalInterface注解

Lambda表达式的省略写法

省略核心：可推导，可省略

  • 参数类型可以省略不写
  • 如果只有一个参数，参数类型可以省略，同时()也可以省略
  • 如果lambda表达式的方法体只有一行，大括号，分号，return可以省略不写，需要同时省略
1
Arrarys.sort(arr,(o1,o2) -> o1 - o2)