算法与数据结构

什么是算法

Algorithm的本意：解决问题的算法

本质：一系列解决问题的，清晰，可执行的计算机指令

接下来，我们更形象的理解什么算法，在我们的生活中随处都可以接触到算法，例如菜谱，如下：

从以上的菜谱看到，清晰，明确的一系列操作后得出一盘可口的鱼香肉丝，就可类比于我们学习算法的一系列解决问题的，清晰，可执行的计算机指令

算法的五大特性

有限性–它是指一个算法必须总是在执行有限的步骤之后结束，并且每一步都必须在有限的时间内完成。
- 这个很容易理解，对于一个算法，我们肯定要让它能够在有限的时间完成任务，不然要花费无穷无尽的时间才能得出结果，那这个算法无疑是失败的。（对于无穷的算法也不能算是失败的算法，也是有一定意义的研究价值）
确定性–顾名思义，对于每种情况下的操作，算法中都有明确的规定，不会产生二义性。
- 举个例子：你的同学有两个叫张三的，如果你不给这两个叫张三的标记他们独有的标签，那么老师在叫张三的时候就会产生二义性，计算机也是如此，它不知道该选择哪一个“张三”。
可行性–它是指算法中的所有操作都可以通过已经实现的操作运算执行有限次来实现。通俗点讲，就是针对实际问题设计的算法，执行后能够达到满意的结果
- 例如：取最大的质数，质数是无穷性的，是取不到最大值的
输入–对于一个算法来说，输入可以是0个或0个以上。
输出–输出必须有一个或一个以上的输出，没有输出的算法没有任何的意义。

线性查找法

一个一个的去查找需要的目标元素。通常会在线性的数据结构中完成。

输入：数组，目标元素

输出：目标元素所在的索引；若不存在，返回-1

代码实现：

/**
 * 线性查找算法
 *
 * @author jingLv
 * @date 2020/11/09
 */
public class LinearSearch {

    /**
     * 外部无法实例化
     */
    private LinearSearch() {
    }

    /**
     * @param data   需要查找的数组
     * @param target 查找的目标元素
     * @return 返回找到的目标元素的索引
     */
    public static int search(int[] data, int target) {
        for (int i = 0; i < data.length; i++) {
            if (data[i] == target) {
                return i;
            }
        }
        // 没有找到目标元素则返回-1
        return -1;
    }

    public static void main(String[] args) {
        int[] data = {24, 18, 12, 9, 16, 66, 32, 4};
        int i = search(data, 16);
        System.out.println("目标元素的位置：" + i);
    }
}

以上的算法只能支持int的数据类型，不能支持其他的数据类型，那么我们如何支持其他类型的线性算法呢？要解决支持多种类型，则我们需要使用Java的特性–泛型。代码改造如下：

/**
 * 线性查找算法
 *
 * @author jingLv
 * @date 2020/11/09
 */
public class LinearSearch {

    /**
     * 外部无法实例化
     */
    private LinearSearch() {
    }

    /**
     * @param data   需要查找的数组
     * @param target 查找的目标元素
     * @param <E>    数据类型
     * @return 返回找到的目标元素的索引
     */
    public static <E> int search(E[] data, E target) {
        for (int i = 0; i < data.length; i++) {
            // 默认比较的是类对象的地址
            if (data[i].equals(target)) {
                // 找到目标元素返回该元素的下标
                return i;
            }
        }
        // 未找到目标元素返回-1
        return -1;
    }

    public static void main(String[] args) {
        Integer[] data = {24, 18, 12, 9, 16, 66, 32, 4};
        int i = search(data, 16);
        System.out.println("目标元素的位置：" + i);
    }
}

注意：泛型只能接收类对象，不能存的数据类型

不可以是基本数据类型，只能是类对象
- 基本数据类型：boolean,byte,char,short,int,long,float,double
每个基本数据类型都有对应的包装类
- 包装类：Boolean,Byte,Character,Short,Integer,Long,Float,Double
如果传入的泛型是基本类型的话，传入对应的包装类即可

自定义类测试算法

之前的例子传递的都是基本类型的数据，我们将线性查找法修改为泛型的方式，就是可以接收任意类型的数据，这时我们传入一个对象进行线性查找，会怎么样呢？我们新建一个Student的对象，代码如下：

package demo.linear;

/**
 * @author jingLv
 * @date 2021/01/18
 */
public class Student {
    private String name;

    public Student(String name) {
        this.name = name;
    }
}

Student进行查找测试：

package demo.linear;

/**
 * 线性查找算法
 *
 * @author jingLv
 * @date 2020/11/09
 */
public class LinearSearch {

    /**
     * 外部无法实例化
     */
    private LinearSearch() {
    }

    /**
     * @param data   需要查找的数组
     * @param target 查找的目标元素
     * @param <E>    数据类型
     * @return 返回找到的目标元素的索引
     */
    public static <E> int search(E[] data, E target) {
        for (int i = 0; i < data.length; i++) {
            // 默认比较的是类对象的地址
            if (data[i].equals(target)) {
                // 找到目标元素返回该元素的下标
                return i;
            }
        }
        // 未找到目标元素返回-1
        return -1;
    }

    public static void main(String[] args) {
        Integer[] data = {24, 18, 12, 9, 16, 66, 32, 4};
        int i = search(data, 16);
        System.out.println("目标元素的位置：" + i);

        Student[] students = {new Student("Alice"), new Student("Bobo"), new Student("Charles")};
        Student bobo = new Student("Bobo");
        int i1 = search(students, bobo);
        System.out.println(i1);
    }
}

执行的结果是-1，现在Student在比较时是默认的使用类对象的地址，上面的代码中”Bobo”是new了两个对象，地址是不一致的，所以在查找时是-1，但是这不符合我们的需求，我们需要的是查找是否有”Bobo”这个字符串，因此我们需要做两个对象的值比较，此时我们就需要Student类重新父类Object中的equals方法，代码如下：

package demo.linear;

/**
 * @author jingLv
 * @date 2021/01/18
 */
public class Student {
    private String name;

    public Student(String name) {
        this.name = name;
    }

    /**
     * 覆盖Object equals方法，完成类对象的值比较
     *
     * @return
     */
    @Override
    public boolean equals(Object student) {
        // 判断当期对象是否是student对象，如果是的话则不需要进行转换
        if (this == student) {
            return true;
        }
        // 判断student是否是空对象，如果是空则返回false
        if (student == null) {
            return false;
        }
        // 判断当前的类对象是否与student的类对象相等，如果不等则返回false
        if (this.getClass() != student.getClass()) {
            return false;
        }
        Student another = (Student) student;
        // 比较的值，不区分大小写
        return this.name.toLowerCase().equals(another.name.toLowerCase());
    }
}

这是在执行测试方法，返回的结果为1。

循环不变量（loop invariant）

什么是循环不变量？

算法在循环的各个阶段，总是存在一个固定不变的特性。找出这个特性证明其固定不变，从而推断出算法是正确的。

必须证明循环不变量满足下面三个性质

初始化：循环的第一次迭代之前，不变量为真
保持：循环的某次迭代之前不变量为真，下次迭代之前仍然为真
终止：循环终止时，不变量依然成立

这个过程类似于数学归纳法，为了证明某条性质成立，需要证明一个基本情况和一个归纳步。第一步“初始化”可以对应“基本情况”，第二步“保持”对应于“归纳步”。而第三步“终止”也许是最重要的，因为我们将用终止时循环不变式来证明算法的正确性。

这里定义循环不变量的窍门就是：结合导致循环终止的条件一起定义循环不变量。

在每一轮循环开始的时候，都满足data[0…i-1]中没有找到目标（或data[0…i)）中没有找到目标这样的性质，条件是不变的，则就是循环不变量。

“证明” 算法的正确性

了解循环不变量，是写正确的代码前提。

写出正确代码：

定义清楚循环不变量
维护循环不变量

函数：定义清楚函数的功能

参考地址：https://www.jianshu.com/p/c202410f7ff2 https://www.jianshu.com/p/1fffff56d260

复杂度分析

复杂度分析：表示算法的性能

通常是看最差的情况，算法运行的上界

数据规模：n=data.length

时间：T

性能：时间与数据规模n成正比，时间复杂被记为O(n)，常数不重要

复杂度描述的是随着数据规模n的增大，算法性能的变化趋势

常见算法复杂度

例子：一个数组中的元素可以组成哪些数据对

for(int i = 0;i < data.length;i++){
  for(int j= i+1;j< data.length;j++){
    // 获得一个数据对(data[i],data[j])
  }
}

时间复杂度是O(n^2)，上面的代码实际上是二分之一N方，j每次都是从i+1开始，在遍历时会减少一半，但是在算复杂度时，常量（二分之一是常量）不重要，因此上面的算法依旧是O(n^2)

例子：遍历一个n*n的二维数组

for(int i = 0;i < n;i++){
  for(int j= 0;j< n;j++){
    // 遍历得到A[i][j]
  }
}

代码的时间复杂度是真正的O(n^2)，i和j都是从数组的0走到n-1

例子：遍历一个a*a的二维数组，且a*a=n

for(int i = 0;i < n;i++){
  for(int j= 0;j< n;j++){
    // 遍历得到A[i][j]
  }
}

代码的复杂度是O(n)，这一段代码和上一段代码中都有n，但是n的含义不一样，上面一段的n是代码二维数组的某个维度为n，则本代码中的n代表是二维数组的总数为n

我们在看复杂度时，一定要理解n是什么！

例子：数字n的二进制位数

while(n) {
  n % 2 // n的二进制中的一位
  n /= 2;
}

代码的时间复杂度O(logn)，本代码的实际复杂度为O(log2n)，如果，数字n的十进制位数呢？时间复杂度为O(log10n)，接下来要是数字n的其他进制位数呢？我们把这样代码的时间复杂度统一为O(logn)对数复杂度，底数忽略掉，底数是多少都是一个常量，也体现出算法复杂度常数不重要

通过上面的例子，我们要理解在计算复杂度不能数循环个数

例子：数字n的所有约数

for(int i = 1;i <= n;i++) {
  if(n % i == 0) {
    // i是n的一个约数
  }
}

时间复杂度是O(n)

for(int i = 1;i*i <= n;i++) {
  if(n % i == 0) {
    // i和n/i是n的两个约数
  }
}

时间复杂度O(根号n)，根号级别的复杂度

例子：长度为n的二进制数字

时间复杂度O(2n次方)指数级别复杂度

例子：长度为n的数组的所有排列

时间复杂度O(n!)，阶乘的复杂度

例子：判断数字n是否是偶数

1	return num % 2;

时间复杂度O(1)常数级复杂度

复杂度的排序

空间复杂度同理

算法性能

数组生成器帮助类

package demo.helper.util;

import java.util.Random;

/**
 * 数组生成器
 *
 * @author jingLv
 * @date 2020/11/13
 */
public class ArrayGenerator {
    /**
     * 构造方法，外部不能实例化
     */
    private ArrayGenerator() {
    }

    /**
     * 生成长度为n的顺序数组
     *
     * @param n 数组长度
     * @return 返回生成的顺序数组
     */
    public static Integer[] generateOrderedArray(int n) {
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i;
        }
        return arr;
    }

    /**
     * 生成长度为n的随机数组
     *
     * @param n     数组长度
     * @param bound 随机数
     * @return 返回生成的随机数组
     */
    public static Integer[] generateRandomArray(int n, int bound) {
        Integer[] arr = new Integer[n];
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            arr[i] = random.nextInt(bound);
        }
        return arr;
    }
}

验证排序算法正确的帮助类

package demo.helper.util;

import demo.sort.insertion.InsertionSort;
import demo.sort.selection.SelectionSort;

/**
 * 验证排序算法正确的帮助类
 *
 * @author jingLv
 * @date 2020/11/18
 */
public class SortingHelper {

    private SortingHelper() {
    }

    /**
     * 验证数组是否有序
     *
     * @param arr 待验证的数组
     * @param <E> 类型
     * @return Boolean
     */
    public static <E extends Comparable<E>> boolean isSorted(E[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1].compareTo(arr[i]) > 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 验证排序方法的时间
     *
     * @param sortName 排序方法名称
     * @param arr      待排序数组
     * @param <E>      类型
     */
    public static <E extends Comparable<E>> void sortTest(String sortName, E[] arr) {
        // 当前纳秒的时间
        long startTime = System.nanoTime();
        if ("SelectionSort".equals(sortName)) {
            SelectionSort.sort(arr);
        } else if ("InsertionSort".equals(sortName)) {
            InsertionSort.sort(arr);
        } else if ("InsertionSort2".equals(sortName)) {
            InsertionSort.sortPlus(arr);
        }
        long endTime = System.nanoTime();
        double time = (endTime - startTime) / 1000000000.0;
        if (!SortingHelper.isSorted(arr)) {
            throw new RuntimeException(sortName + " failed");
        }
        System.out.println(String.format("%s, n = %d : %f s", sortName, arr.length, time));
    }

    /**
     * 交换数组的元素
     *
     * @param arr 数组
     * @param i   元素i
     * @param j   元素j
     * @param <E> 类型
     */
    public static <E> void swap(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

根据以上提供的两个帮助类，可以自动生成不同长度的数组，及测试数组处理的时间，根据结果对比查看算法的性能，示例如下：

package demo.sort.insertion;

import demo.helper.util.ArrayGenerator;
import demo.helper.util.SortingHelper;

import java.util.Arrays;

/**
 * @author jingLv
 * @date 2020/11/19
 */
public class InsertionSort {

    private InsertionSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            // 将arr[i]插入到合适的位置
            for (int j = i; j - 1 >= 0; j--) {
                if (arr[j].compareTo(arr[j - 1]) < 0) {
                    SortingHelper.swap(arr, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }

    public static <E extends Comparable<E>> void sortMerge(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            // 将if语句合并到一起
            for (int j = i; j - 1 >= 0 && arr[j].compareTo(arr[j - 1]) < 0; j--) {
                SortingHelper.swap(arr, j, j - 1);
            }
        }
    }

    public static <E extends Comparable<E>> void sortPlus(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            // 暂存元素
            E t = arr[i];
            int j;
            for (j = i; j - 1 >= 0 && t.compareTo(arr[j - 1]) < 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = t;
        }
    }

    public static void main(String[] args) {
        int[] dataSize = {1000, 10000};
        for (int n : dataSize) {
            Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
            Integer[] arr2 = Arrays.copyOf(arr, arr.length);
            SortingHelper.sortTest("InsertionSort", arr);
            SortingHelper.sortTest("InsertionSort2", arr2);
        }
    }
}

执行结果：